delayacct_init()

delayacct_init()

kernel/delayacct.c

void delayacct_init(void)
{
        delayacct_cache = KMEM_CACHE(task_delay_info, SLAB_PANIC);
        delayacct_tsk_init(&init_task);
}

CONFIG_TASK_DELAY_ACCT 커널 옵션을 사용하는 경우 task에 대한 각종 지연 stat을 얻을 수 있다.

  • cpu, 동기 블록 입출력 완료 및 페이지 스와핑과 같은 시스템 자원을 기다리는 작업에 소요되는 시간에 대한 정보를 수집합니다.
  • “nodelayacct” 커널 파라메터를 사용하는 경우 delay accounting 기능을 disable한다.

 

__delayacct_tsk_init()

kernel/delayacct.c

void __delayacct_tsk_init(struct task_struct *tsk)
{
        tsk->delays = kmem_cache_zalloc(delayacct_cache, GFP_KERNEL);
        if (tsk->delays)
                spin_lock_init(&tsk->delays->lock);
}

요청 태스크의 delays 멤버에 delayacct_cache 구조체를 할당받은 후 초기화한다.

 

delayacct_setup_disable()

kernel/delayacct.c

int delayacct_on __read_mostly = 1;     /* Delay accounting turned on/off */
EXPORT_SYMBOL_GPL(delayacct_on);
struct kmem_cache *delayacct_cache;

static int __init delayacct_setup_disable(char *str)
{
        delayacct_on = 0;
        return 1;
}
__setup("nodelayacct", delayacct_setup_disable);

“nodelayacct” 커널 파라메터를 사용하는 경우 delay accounting 기능을 disable한다.

 

Per-task Delay Accounting

delayacct_freepages_start()

include/linux/delayacct.h

static inline void delayacct_freepages_start(void)
{
        if (current->delays)
                __delayacct_freepages_start();
}

태스크의 delay accounting에 사용하기 위해 현재 시작 clock을 기록한다.

 

__delayacct_blkio_start()

kernel/delayacct.c

void __delayacct_freepages_start(void)
{
        current->delays->freepages_start = ktime_get_ns();
}

태스크의 delay accounting에 사용하기 위해 현재 시작 clock을 기록한다.

 

delayacct_freepages_end()

include/linux/delayacct.h

static inline void delayacct_freepages_end(void)
{
        if (current->delays)
                __delayacct_freepages_end();
}

태스크의 delay accounting에 사용하기 위해 시작 clock에서 현재 clock을 빼서 기록한다.

 

__delayacct_freepages_end()

kernel/delayacct.c

void __delayacct_freepages_end(void)
{
        delayacct_end(&current->delays->freepages_start,
                        &current->delays->freepages_delay,
                        &current->delays->freepages_count);
}

태스크의 delay accounting에 사용하기 위해 현재 clock에서 freepages_start clock을 빼서 freepages_delay에 delay time을 추가하고 freepages_count를 증가시킨다.

 

delayacct_end()

kernel/delayacct.c

/*
 * Finish delay accounting for a statistic using its timestamps (@start),
 * accumalator (@total) and @count
 */
static void delayacct_end(u64 *start, u64 *total, u32 *count)
{
        s64 ns = ktime_get_ns() - *start;
        unsigned long flags;

        if (ns > 0) {
                spin_lock_irqsave(&current->delays->lock, flags);
                *total += ns;
                (*count)++;
                spin_unlock_irqrestore(&current->delays->lock, flags);
        }
}

delay accounting에 사용하기 위해 현재 clock에서 인수로 전달받은 start clock을 빼서 total에 추가 하고 count를 증가시킨다.

 

getdelays 유틸리티 빌드 및 사용

  • Documentation/accounting/getdelay.c를 컴파일하여 사용한다.
    • gcc -I/usr/src/linux/include getdelays.c -o getdelays

 

./getdelays 
getdelays [-dilv] [-w logfile] [-r bufsize] [-m cpumask] [-t tgid] [-p pid]
  -d: print delayacct stats
  -i: print IO accounting (works only with -p)
  -l: listen forever
  -v: debug on
  -C: container path

 

참고

 

 

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를 가리키는 포인터

 

참고

numa_policy_init()

 

numa_policy_init()

mm/mempolicy.c

void __init numa_policy_init(void)
{
        nodemask_t interleave_nodes; 
        unsigned long largest = 0;
        int nid, prefer = 0;

        policy_cache = kmem_cache_create("numa_policy",
                                         sizeof(struct mempolicy),
                                         0, SLAB_PANIC, NULL);

        sn_cache = kmem_cache_create("shared_policy_node",
                                     sizeof(struct sp_node),
                                     0, SLAB_PANIC, NULL);

        for_each_node(nid) {
                preferred_node_policy[nid] = (struct mempolicy) {
                        .refcnt = ATOMIC_INIT(1),
                        .mode = MPOL_PREFERRED,
                        .flags = MPOL_F_MOF | MPOL_F_MORON,
                        .v = { .preferred_node = nid, },
                };
        }
                
        /*
         * Set interleaving policy for system init. Interleaving is only
         * enabled across suitably sized nodes (default is >= 16MB), or
         * fall back to the largest node if they're all smaller.
         */
        nodes_clear(interleave_nodes);
        for_each_node_state(nid, N_MEMORY) {
                unsigned long total_pages = node_present_pages(nid);

                /* Preserve the largest node */
                if (largest < total_pages) {
                        largest = total_pages;
                        prefer = nid;
                }

                /* Interleave this node? */
                if ((total_pages << PAGE_SHIFT) >= (16 << 20))
                        node_set(nid, interleave_nodes);
        }

        /* All too small, use the largest */
        if (unlikely(nodes_empty(interleave_nodes)))
                node_set(prefer, interleave_nodes);

        if (do_set_mempolicy(MPOL_INTERLEAVE, 0, &interleave_nodes))
                pr_err("%s: interleaving failed\n", __func__);

        check_numabalancing_enable();
}

 

  • 코드 라인 07~13에서 mempolicy 구조체 타입으로 전역 policy_cache kmem 캐시와 sp_node 구조체 타입으로 전역 sn_cache kmem 캐시를 구성한다.
  • 코드 라인 15~22에서 전체 노드에 대해 preferred_node_policy[] 배열을 초기화한다.
  • 코드 라인 29~41에서 interleave 노드를 초기화한다. 16M 이상의 모든 메모리 노드를 interleave 노드에 참여 시킨다.
  • 코드 라인 44~45에서 만일 참여한 노드가 하나도 없는 경우 가장 큰 노드를 interleave 노드에 참여시킨다.
  • 코드 라인 47~48에서 interleave 메모리 정책을 설정한다.
  • 코드 라인 50에서 NUMA 밸런싱을 설정한다.

 

mm/mempolicy.c

static struct mempolicy preferred_node_policy[MAX_NUMNODES];

 

do_set_mempolicy()

mm/mempolicy.c

/* Set the process memory policy */
static long do_set_mempolicy(unsigned short mode, unsigned short flags,
                             nodemask_t *nodes)
{
        struct mempolicy *new, *old;
        NODEMASK_SCRATCH(scratch);
        int ret;

        if (!scratch)
                return -ENOMEM;

        new = mpol_new(mode, flags, nodes);
        if (IS_ERR(new)) {
                ret = PTR_ERR(new);
                goto out;
        }

        task_lock(current);
        ret = mpol_set_nodemask(new, nodes, scratch);
        if (ret) {
                task_unlock(current);
                mpol_put(new);
                goto out;
        }
        old = current->mempolicy;
        current->mempolicy = new;
        if (new && new->mode == MPOL_INTERLEAVE &&
            nodes_weight(new->v.nodes))
                current->il_next = first_node(new->v.nodes);
        task_unlock(current);
        mpol_put(old);
        ret = 0;
out:
        NODEMASK_SCRATCH_FREE(scratch);
        return ret;
}

요청한 메모리 정책 모드를 새로 만들고 설정한 후 현재 태스크의 메모리 정책에 대입시킨다.

 

mpol_new()

mm/mempolicy.c

/*
 * This function just creates a new policy, does some check and simple
 * initialization. You must invoke mpol_set_nodemask() to set nodes.
 */
static struct mempolicy *mpol_new(unsigned short mode, unsigned short flags,
                                  nodemask_t *nodes)
{
        struct mempolicy *policy;

        pr_debug("setting mode %d flags %d nodes[0] %lx\n",
                 mode, flags, nodes ? nodes_addr(*nodes)[0] : NUMA_NO_NODE);

        if (mode == MPOL_DEFAULT) {
                if (nodes && !nodes_empty(*nodes))
                        return ERR_PTR(-EINVAL);
                return NULL;
        }
        VM_BUG_ON(!nodes);

        /*
         * MPOL_PREFERRED cannot be used with MPOL_F_STATIC_NODES or
         * MPOL_F_RELATIVE_NODES if the nodemask is empty (local allocation).
         * All other modes require a valid pointer to a non-empty nodemask.
         */
        if (mode == MPOL_PREFERRED) {
                if (nodes_empty(*nodes)) {
                        if (((flags & MPOL_F_STATIC_NODES) ||
                             (flags & MPOL_F_RELATIVE_NODES)))
                                return ERR_PTR(-EINVAL);
                }
        } else if (mode == MPOL_LOCAL) {
                if (!nodes_empty(*nodes))
                        return ERR_PTR(-EINVAL);
                mode = MPOL_PREFERRED;
        } else if (nodes_empty(*nodes))
                return ERR_PTR(-EINVAL);
        policy = kmem_cache_alloc(policy_cache, GFP_KERNEL);
        if (!policy)
                return ERR_PTR(-ENOMEM);
        atomic_set(&policy->refcnt, 1);
        policy->mode = mode;
        policy->flags = flags;

        return policy;
}

새로운 메모리 정책을 생성한다.

 

mpol_set_nodemask()

mm/mempolicy.c

/*
 * mpol_set_nodemask is called after mpol_new() to set up the nodemask, if
 * any, for the new policy.  mpol_new() has already validated the nodes
 * parameter with respect to the policy mode and flags.  But, we need to
 * handle an empty nodemask with MPOL_PREFERRED here.
 *
 * Must be called holding task's alloc_lock to protect task's mems_allowed
 * and mempolicy.  May also be called holding the mmap_semaphore for write.
 */
static int mpol_set_nodemask(struct mempolicy *pol,
                     const nodemask_t *nodes, struct nodemask_scratch *nsc)
{
        int ret;

        /* if mode is MPOL_DEFAULT, pol is NULL. This is right. */
        if (pol == NULL)
                return 0;
        /* Check N_MEMORY */
        nodes_and(nsc->mask1,
                  cpuset_current_mems_allowed, node_states[N_MEMORY]);

        VM_BUG_ON(!nodes);
        if (pol->mode == MPOL_PREFERRED && nodes_empty(*nodes))
                nodes = NULL;   /* explicit local allocation */
        else {
                if (pol->flags & MPOL_F_RELATIVE_NODES)
                        mpol_relative_nodemask(&nsc->mask2, nodes, &nsc->mask1);
                else
                        nodes_and(nsc->mask2, *nodes, nsc->mask1);

                if (mpol_store_user_nodemask(pol))
                        pol->w.user_nodemask = *nodes;
                else
                        pol->w.cpuset_mems_allowed =
                                                cpuset_current_mems_allowed;
        }

        if (nodes)
                ret = mpol_ops[pol->mode].create(pol, &nsc->mask2);
        else
                ret = mpol_ops[pol->mode].create(pol, NULL);
        return ret;
}

 

mpol_relative_nodemask()

mm/mempolicy.c

static void mpol_relative_nodemask(nodemask_t *ret, const nodemask_t *orig,
                                   const nodemask_t *rel)
{
        nodemask_t tmp;
        nodes_fold(tmp, *orig, nodes_weight(*rel));
        nodes_onto(*ret, tmp, *rel);
}

 

 

 

mpol_op[] 구조체 배열

static const struct mempolicy_operations mpol_ops[MPOL_MAX] = {
        [MPOL_DEFAULT] = {
                .rebind = mpol_rebind_default,
        },
        [MPOL_INTERLEAVE] = {
                .create = mpol_new_interleave,
                .rebind = mpol_rebind_nodemask,
        },
        [MPOL_PREFERRED] = {
                .create = mpol_new_preferred,
                .rebind = mpol_rebind_preferred,
        },
        [MPOL_BIND] = {
                .create = mpol_new_bind,
                .rebind = mpol_rebind_nodemask,
        },
};

 

check_numabalancing_enable()

mm/mempolicy.c

#ifdef CONFIG_NUMA_BALANCING
static int __initdata numabalancing_override;

static void __init check_numabalancing_enable(void)
{
        bool numabalancing_default = false;

        if (IS_ENABLED(CONFIG_NUMA_BALANCING_DEFAULT_ENABLED))
                numabalancing_default = true;

        /* Parsed by setup_numabalancing. override == 1 enables, -1 disables */
        if (numabalancing_override)
                set_numabalancing_state(numabalancing_override == 1);

        if (num_online_nodes() > 1 && !numabalancing_override) {
                pr_info("%s automatic NUMA balancing. "
                        "Configure with numa_balancing= or the "
                        "kernel.numa_balancing sysctl",
                        numabalancing_default ? "Enabling" : "Disabling");
                set_numabalancing_state(numabalancing_default);
        }
} 
#endif

NUMA 밸런싱을 설정한다.

  • 코드 라인 12~13에서  “numa_balancing=enable” 커널 파라메터가 설정된 경우 전역 numabalancing_enabled를 true로 설정한다.
  • 코드 라인 15~21에서 CONFIG_NUMA_BALANCING_DEFAULT_ENABLED 커널 옵션이 사용된 커널에서 온라인 노드가 2개 이상인 경우도 전역 numabalancing_enabled를 true로 설정한다.

 

구조체

mempolicy 구조체

/*
 * Describe a memory policy.
 *
 * A mempolicy can be either associated with a process or with a VMA.
 * For VMA related allocations the VMA policy is preferred, otherwise
 * the process policy is used. Interrupts ignore the memory policy
 * of the current process.
 *
 * Locking policy for interlave:
 * In process context there is no locking because only the process accesses
 * its own state. All vma manipulation is somewhat protected by a down_read on
 * mmap_sem.
 *
 * Freeing policy:
 * Mempolicy objects are reference counted.  A mempolicy will be freed when
 * mpol_put() decrements the reference count to zero.
 *
 * Duplicating policy objects:
 * mpol_dup() allocates a new mempolicy and copies the specified mempolicy
 * to the new storage.  The reference count of the new object is initialized
 * to 1, representing the caller of mpol_dup().
 */
struct mempolicy {
        atomic_t refcnt;
        unsigned short mode;    /* See MPOL_* above */
        unsigned short flags;   /* See set_mempolicy() MPOL_F_* above */
        union {
                short            preferred_node; /* preferred */
                nodemask_t       nodes;         /* interleave/bind */
                /* undefined for default */
        } v;
        union {
                nodemask_t cpuset_mems_allowed; /* relative to these nodes */
                nodemask_t user_nodemask;       /* nodemask passed by user */
        } w; 
};

 

 

mempolicy_operations 구조체

mm/mempolicy.c

static const struct mempolicy_operations {
        int (*create)(struct mempolicy *pol, const nodemask_t *nodes);
        /*
         * If read-side task has no lock to protect task->mempolicy, write-side
         * task will rebind the task->mempolicy by two step. The first step is
         * setting all the newly nodes, and the second step is cleaning all the
         * disallowed nodes. In this way, we can avoid finding no node to alloc
         * page.
         * If we have a lock to protect task->mempolicy in read-side, we do
         * rebind directly.
         *
         * step:
         *      MPOL_REBIND_ONCE - do rebind work at once
         *      MPOL_REBIND_STEP1 - set all the newly nodes
         *      MPOL_REBIND_STEP2 - clean all the disallowed nodes
         */
        void (*rebind)(struct mempolicy *pol, const nodemask_t *nodes,
                        enum mpol_rebind_step step);
} mpol_ops[MPOL_MAX];

 

 

Policy 관련 enum

/*
 * Both the MPOL_* mempolicy mode and the MPOL_F_* optional mode flags are
 * passed by the user to either set_mempolicy() or mbind() in an 'int' actual.
 * The MPOL_MODE_FLAGS macro determines the legal set of optional mode flags.
 */

/* Policies */
enum {
        MPOL_DEFAULT,
        MPOL_PREFERRED,
        MPOL_BIND, 
        MPOL_INTERLEAVE,
        MPOL_LOCAL,
        MPOL_MAX,       /* always last member of enum */
};

 

참고

Zoned Allocator -14- (Kswapd & Kcompactd)

<kernel v5.0>

Kswapd & Kcompactd

노드마다 kswapd와 kcompactd가 동작하며 free 메모리가 일정량 이상 충분할 때에는 잠들어(sleep) 있다. 그런데 페이지 할당자가 order 페이지 할당을 시도하다 free 페이지가 부족해 low 워터마크 기준을 충족하지 못하는 순간 kswapd 및 kcompactd를 깨운다. kswapd는 자신의 노드에서 페이지 회수를 진행하고, kcompactd는 compaction을 진행하는데 모든 노드에 대해 밸런스하게 high 워터마크 기준을 충족하게 되면 스스로 sleep 한다.

 

kswapd 초기화

kswapd_init()

mm/vmscan.c

static int __init kswapd_init(void)
{
        int nid, ret;

        swap_setup();
        for_each_node_state(nid, N_MEMORY)
                kswapd_run(nid);
        ret = cpuhp_setup_state_nocalls(CPUHP_AP_ONLINE_DYN,
                                        "mm/vmscan:online", kswapd_cpu_online,
                                        NULL);
        WARN_ON(ret < 0);
        return 0;
}

module_init(kswapd_init)

kswapd를 사용하기 위해 초기화한다.

  • 코드 라인 5에서 kswapd 실행 전에 준비한다.
  • 코드 라인 6~7에서 모든 메모리 노드에 대해 kswapd를 실행시킨다.
  • 코드 라인 8~10에서 cpu가 hot-plug를 통해 CPUHP_AP_ONLINE_DYN 상태로 변경될 때 kswapd_cpu_online() 함수가 호출될 수 있도록 등록한다.

 

swap_setup()

mm/swap.c

/*
 * Perform any setup for the swap system
 */
void __init swap_setup(void)
{
        unsigned long megs = totalram_pages >> (20 - PAGE_SHIFT); 

        /* Use a smaller cluster for small-memory machines */
        if (megs < 16)                          
                page_cluster = 2;
        else
                page_cluster = 3;
        /* 
         * Right now other parts of the system means that we
         * _really_ don't want to cluster much more
         */
}

kswapd 실행 전에 준비한다.

  • 코드 라인 3~9에서 전역 total 램이 16M 이하이면 page_cluster에 2를 대입하고 그렇지 않으면 3을 대입한다.

 

kswapd_run()

mm/vmscan.c

/*
 * This kswapd start function will be called by init and node-hot-add.
 * On node-hot-add, kswapd will moved to proper cpus if cpus are hot-added.
 */
int kswapd_run(int nid)
{
        pg_data_t *pgdat = NODE_DATA(nid);
        int ret = 0;

        if (pgdat->kswapd)
                return 0;

        pgdat->kswapd = kthread_run(kswapd, pgdat, "kswapd%d", nid);
        if (IS_ERR(pgdat->kswapd)) {
                /* failure at boot is fatal */
                BUG_ON(system_state == SYSTEM_BOOTING);
                pr_err("Failed to start kswapd on node %d\n", nid);
                ret = PTR_ERR(pgdat->kswapd);
                pgdat->kswapd = NULL;
        }
        return ret;
}

kswapd 스레드를 동작시킨다.

  • 코드 라인 3~7에서 @nid 노드의 kswapd 태스크가 지정되지 않은 경우 0을 반환한다.
  • 코드 라인 9~16에서 kswapd 스레드를 동작시킨다.

 

kswapd 동작

kswapd()

mm/vmscan.c

/*
 * The background pageout daemon, started as a kernel thread
 * from the init process.
 *
 * This basically trickles out pages so that we have _some_
 * free memory available even if there is no other activity
 * that frees anything up. This is needed for things like routing
 * etc, where we otherwise might have all activity going on in
 * asynchronous contexts that cannot page things out.
 *
 * If there are applications that are active memory-allocators
 * (most normal use), this basically shouldn't matter.
 */
static int kswapd(void *p)
{
        unsigned int alloc_order, reclaim_order;
        unsigned int classzone_idx = MAX_NR_ZONES - 1;
        pg_data_t *pgdat = (pg_data_t*)p;
        struct task_struct *tsk = current;

        struct reclaim_state reclaim_state = {
                .reclaimed_slab = 0,
        };
        const struct cpumask *cpumask = cpumask_of_node(pgdat->node_id);

        if (!cpumask_empty(cpumask))
                set_cpus_allowed_ptr(tsk, cpumask);
        current->reclaim_state = &reclaim_state;

        /*
         * Tell the memory management that we're a "memory allocator",
         * and that if we need more memory we should get access to it
         * regardless (see "__alloc_pages()"). "kswapd" should
         * never get caught in the normal page freeing logic.
         *
         * (Kswapd normally doesn't need memory anyway, but sometimes
         * you need a small amount of memory in order to be able to
         * page out something else, and this flag essentially protects
         * us from recursively trying to free more memory as we're
         * trying to free the first piece of memory in the first place).
         */
        tsk->flags |= PF_MEMALLOC | PF_SWAPWRITE | PF_KSWAPD;
        set_freezable();

        pgdat->kswapd_order = 0;
        pgdat->kswapd_classzone_idx = MAX_NR_ZONES;
        for ( ; ; ) {
                bool ret;

                alloc_order = reclaim_order = pgdat->kswapd_order;
                classzone_idx = kswapd_classzone_idx(pgdat, classzone_idx);

kswapd_try_sleep:
                kswapd_try_to_sleep(pgdat, alloc_order, reclaim_order,
                                        classzone_idx);

                /* Read the new order and classzone_idx */
                alloc_order = reclaim_order = pgdat->kswapd_order;
                classzone_idx = kswapd_classzone_idx(pgdat, 0);
                pgdat->kswapd_order = 0;
                pgdat->kswapd_classzone_idx = MAX_NR_ZONES;

                ret = try_to_freeze();
                if (kthread_should_stop())
                        break;

                /*
                 * We can speed up thawing tasks if we don't call balance_pgdat
                 * after returning from the refrigerator
                 */
                if (ret)
                        continue;

                /*
                 * Reclaim begins at the requested order but if a high-order
                 * reclaim fails then kswapd falls back to reclaiming for
                 * order-0. If that happens, kswapd will consider sleeping
                 * for the order it finished reclaiming at (reclaim_order)
                 * but kcompactd is woken to compact for the original
                 * request (alloc_order).
                 */
                trace_mm_vmscan_kswapd_wake(pgdat->node_id, classzone_idx,
                                                alloc_order);
                reclaim_order = balance_pgdat(pgdat, alloc_order, classzone_idx);
                if (reclaim_order < alloc_order)
                        goto kswapd_try_sleep;
        }

        tsk->flags &= ~(PF_MEMALLOC | PF_SWAPWRITE | PF_KSWAPD);
        current->reclaim_state = NULL;

        return 0;
}

각 노드에서 동작되는 kswapd 스레드는 각 노드에서 동작하는 zone에 대해 free 페이지가 low 워터마크 이하로 내려가는 경우 백그라운드에서 페이지 회수를 진행하고 high 워터마크 이상이 되는 경우 페이지 회수를 멈춘다.

  • 코드 라인 5~14에서 요청 노드에서 동작하는 온라인 cpumask를 읽어와서 현재 태스크에 설정한다.
    • 요청 노드의 cpumask를 현재 task에 cpus_allowed 등을 설정한다.
  • 코드 라인 15에서 현재 태스크의 reclaim_state가 초기화된 reclaim_state 구조체를 가리키게 한다.
  • 코드 라인 29에서 현재 태스크의 플래그에 PF_MEMALLOC, PF_SWAPWRITE 및 PF_KSWAPD를 설정한다.
    • PF_MEMALLOC
      • 메모리 reclaim을 위한 태스크로 워터 마크 제한 없이 할당할 수 있도록 한다.
    • PF_SWAPWRITE
      • anon 메모리에 대해 swap 기록 요청을 한다.
    • PF_KSWAPD
      • kswapd task를 의미한다.
  • 코드 라인 30에서 현재 태스크를 freeze할 수 있도록 PF_NOFREEZE 플래그를 제거한다.
  • 코드 라인 32~33에서 kswapd_order를 0부터 시작하게 하고 kswapd_classzone_idx는 가장 상위부터 할 수 있도록 MAX_NR_ZONES를 대입해둔다.
  • 코드 라인 34~38에서 alloc_order와 reclaim_order를 노드의 kswapd가 진행하는 order를 사용한다. 그리고 대상 존인 classzone_idx를 가져온다.
  • 코드 라인 40~42에서 try_sleep: 레이블이다. kswapd가 슬립하도록 시도한다.
  • 코드 라인 45~46에서 alloc_order와 reclaim_order를 외부에서 요청한 order와 zone을 적용시킨다.
  • 코드 라인 47~48에서 kwapd_order를 0으로 리셋하고, kswapd_classzone_idx는 가장 상위부터 할 수 있도록 MAX_NR_ZONES를 대입해둔다.
  • 코드 라인 50에서 현재 태스크 kswapd에 대해 freeze 요청이 있는 경우 freeze 시도한다.
  • 코드 라인 51~52에서 현재 태스크의 KTHREAD_SHOULD_STOP 플래그 비트가 설정된 경우 루프를 탈출하고 스레드 종료 처리한다.
  • 코드 라인 58~59에서 freeze 된 적이 있으면 빠른 처리를 위해 노드 밸런스를 동작시키지 않고 계속 진행한다.
  • 코드 라인 71에서 freeze 한 적이 없었던 경우이다. order 페이지와 존을 대상으로 페이지 회수를 진행한다.
  • 코드 라인 72~73에서 요청한 order에서 회수가 실패한 경우 order 0 및 해당 존에서 다시 시도하기 위해 try_sleep: 레이블로 이동한다.
  • 코드 라인 74에서 요청한 order에서 회수가 성공한 경우에는 루프를 계속 반복한다.
  • 코드 라인 76~79에서 kswapd 스레드의 처리를 완료시킨다.

 

kswapd_try_to_sleep()

mm/vmscan.c

static void kswapd_try_to_sleep(pg_data_t *pgdat, int alloc_order, int reclaim_order,
                                unsigned int classzone_idx)
{
        long remaining = 0;
        DEFINE_WAIT(wait);

        if (freezing(current) || kthread_should_stop())
                return;

        prepare_to_wait(&pgdat->kswapd_wait, &wait, TASK_INTERRUPTIBLE);

        /*
         * Try to sleep for a short interval. Note that kcompactd will only be
         * woken if it is possible to sleep for a short interval. This is
         * deliberate on the assumption that if reclaim cannot keep an
         * eligible zone balanced that it's also unlikely that compaction will
         * succeed.
         */
        if (prepare_kswapd_sleep(pgdat, reclaim_order, classzone_idx)) {
                /*
                 * Compaction records what page blocks it recently failed to
                 * isolate pages from and skips them in the future scanning.
                 * When kswapd is going to sleep, it is reasonable to assume
                 * that pages and compaction may succeed so reset the cache.
                 */
                reset_isolation_suitable(pgdat);

                /*
                 * We have freed the memory, now we should compact it to make
                 * allocation of the requested order possible.
                 */
                wakeup_kcompactd(pgdat, alloc_order, classzone_idx);

                remaining = schedule_timeout(HZ/10);

                /*
                 * If woken prematurely then reset kswapd_classzone_idx and
                 * order. The values will either be from a wakeup request or
                 * the previous request that slept prematurely.
                 */
                if (remaining) {
                        pgdat->kswapd_classzone_idx = kswapd_classzone_idx(pgdat, classzone_idx);
                        pgdat->kswapd_order = max(pgdat->kswapd_order, reclaim_order);
                }

                finish_wait(&pgdat->kswapd_wait, &wait);
                prepare_to_wait(&pgdat->kswapd_wait, &wait, TASK_INTERRUPTIBLE);
        }

        /*
         * After a short sleep, check if it was a premature sleep. If not, then
         * go fully to sleep until explicitly woken up.
         */
        if (!remaining &&
            prepare_kswapd_sleep(pgdat, reclaim_order, classzone_idx)) {
                trace_mm_vmscan_kswapd_sleep(pgdat->node_id);

                /*
                 * vmstat counters are not perfectly accurate and the estimated
                 * value for counters such as NR_FREE_PAGES can deviate from the
                 * true value by nr_online_cpus * threshold. To avoid the zone
                 * watermarks being breached while under pressure, we reduce the
                 * per-cpu vmstat threshold while kswapd is awake and restore
                 * them before going back to sleep.
                 */
                set_pgdat_percpu_threshold(pgdat, calculate_normal_threshold);

                if (!kthread_should_stop())
                        schedule();

                set_pgdat_percpu_threshold(pgdat, calculate_pressure_threshold);
        } else {
                if (remaining)
                        count_vm_event(KSWAPD_LOW_WMARK_HIT_QUICKLY);
                else
                        count_vm_event(KSWAPD_HIGH_WMARK_HIT_QUICKLY);
        }
        finish_wait(&pgdat->kswapd_wait, &wait);
}

노드에 대해 요청 order 및 zone 까지 free 페이지가 high 워터마크 기준으로 밸런스하게 할당할 수 있는 상태라면 sleep 한다.

  • 코드 라인 7~8에서 freeze 요청이 있는 경우 함수를 빠져나간다.
  • 코드 라인 10에서 현재 태스크를 kswapd_wait에 추가하여 sleep할 준비를 한다.
  • 코드 섹션 19~48에서 요청 zone 까지 그리고 요청 order에 대해 free 페이지가 밸런스된 high 워터마크 기준을 충족하는 경우의 처리이다.
    • 최근에 direct-compaction이 완료되어 해당 존에서 compaction을 다시 처음부터 시작할 수 있도록 존에 compact_blockskip_flush이 설정된다. 이렇게 설정된 존들에 대해 skip 블럭 비트를 모두 클리어한다.
    • compactd 스레드를 깨운다.
    • 0.1초를 sleep 한다.  만일 중간에 깬 경우 노드에 kswapd가 처리중인 zone과 order를 기록해둔다.
    • 다시 슬립할 준비를 한다.
  • 코드 섹션 54~71에서 중간에 깨어나지 않고 0.1초를 완전히 슬립하였고, 여전히 요청 zone 까지 그리고 요청 order에 대해 free 페이지가 확보되어 밸런스된 high 워터마크 기준을 충족하면 다음과 같이 처리한다.
    • NR_FREE_PAGES 등의 vmstat을 정밀하게 계산할 필요 여부를 per-cpu 스레졸드라고 하는데, 이를 일반적인 기준의 스레졸드로 지정하도록 노드에 포함된 각 zone에 대해 normal한 스레졸드 값을 지정한다.
    • 스레드 종료 요청이 아닌 경우 sleep한다.
    • kswapd가 깨어났다는 이유는 메모리 압박 상황이 되었다라는 의미이다. 따라서 이번에는 per-cpu 스레졸드 값으로 pressure한 스레졸드 값을  사용하기 지정한다.
  • 코드 섹션 72~77에서 메모리 부족 상황이 빠르게 온 경우이다. 슬립하자마자 깨어났는데 조건에 따라 관련 카운터를 다음과 같이 처리한다.
    • 0.1초간 잠시 sleep 하는 와중에 다시 메모리 부족을 이유로 현재 스레드인 kswapd가 깨어난 경우에는 KSWAPD_LOW_WMARK_HIT_QUICKLY 카운터를 증가시킨다.
    • 0.1초 슬립한 후에도 high 워터마크 기준을 충족할 만큼 메모리가 확보되지 못해 슬립하지 못하는 상황이다. 이러한 경우 KSWAPD_HIGH_WMARK_HIT_QUICKLY 카운터를 증가시킨다.
  • 코드 섹션 78에서 kswapd_wait 에서 현재 태스크를 제거한다.

 

다음 그림은 kswapd_try_to_sleep() 함수를 통해 kswapd가 high 워터마크 기준을 충족하면 슬립하는 과정을 보여준다.

 


밸런스될 때까지 페이지 회수

balance_pgdat()

mm/vmscan.c -1/3-

/*
 * For kswapd, balance_pgdat() will reclaim pages across a node from zones
 * that are eligible for use by the caller until at least one zone is
 * balanced.
 *
 * Returns the order kswapd finished reclaiming at.
 *
 * kswapd scans the zones in the highmem->normal->dma direction.  It skips
 * zones which have free_pages > high_wmark_pages(zone), but once a zone is
 * found to have free_pages <= high_wmark_pages(zone), any page is that zone
 * or lower is eligible for reclaim until at least one usable zone is
 * balanced.
 */
static int balance_pgdat(pg_data_t *pgdat, int order, int classzone_idx)
{
        int i;
        unsigned long nr_soft_reclaimed;
        unsigned long nr_soft_scanned;
        unsigned long pflags;
        unsigned long nr_boost_reclaim;
        unsigned long zone_boosts[MAX_NR_ZONES] = { 0, };
        bool boosted;
        struct zone *zone;
        struct scan_control sc = {
                .gfp_mask = GFP_KERNEL,
                .order = order,
                .may_unmap = 1,
        };

        psi_memstall_enter(&pflags);
        __fs_reclaim_acquire();

        count_vm_event(PAGEOUTRUN);

        /*
         * Account for the reclaim boost. Note that the zone boost is left in
         * place so that parallel allocations that are near the watermark will
         * stall or direct reclaim until kswapd is finished.
         */
        nr_boost_reclaim = 0;
        for (i = 0; i <= classzone_idx; i++) {
                zone = pgdat->node_zones + i;
                if (!managed_zone(zone))
                        continue;

                nr_boost_reclaim += zone->watermark_boost;
                zone_boosts[i] = zone->watermark_boost;
        }
        boosted = nr_boost_reclaim;

restart:
        sc.priority = DEF_PRIORITY;
        do {
                unsigned long nr_reclaimed = sc.nr_reclaimed;
                bool raise_priority = true;
                bool balanced;
                bool ret;

                sc.reclaim_idx = classzone_idx;

                /*
                 * If the number of buffer_heads exceeds the maximum allowed
                 * then consider reclaiming from all zones. This has a dual
                 * purpose -- on 64-bit systems it is expected that
                 * buffer_heads are stripped during active rotation. On 32-bit
                 * systems, highmem pages can pin lowmem memory and shrinking
                 * buffers can relieve lowmem pressure. Reclaim may still not
                 * go ahead if all eligible zones for the original allocation
                 * request are balanced to avoid excessive reclaim from kswapd.
                 */
                if (buffer_heads_over_limit) {
                        for (i = MAX_NR_ZONES - 1; i >= 0; i--) {
                                zone = pgdat->node_zones + i;
                                if (!managed_zone(zone))
                                        continue;

                                sc.reclaim_idx = i;
                                break;
                        }
                }

우선 순위를 12부터 1까지 높여가며 페이지 회수 및 compaction을 진행하여 free 페이지가 요청 order 및 zone까지 밸런스하게 high 워터마크 기준을  충족할 때까지 진행한다.

  • 코드 라인 11~15에서 준비한 scan_control 구조체에 매핑된 페이지를 언맵할 수 있게 may_unmap=1로 설정한다.
  • 코드 라인 17에서 메모리 부족으로 인한 현재 태스크의 psi 산출을 시작하는 지점이다.
  • 코드 라인 20에서 PAGEOUTRUN 카운터를 증가시킨다.
  • 코드 라인 27~36에서 요청한 classzone_idx 이하의 존들을 순회하며 워터마크 부스트 값을 합산하여 boosted 및 nr_boost_reclaim에 대입한다. 그리고 존별 부스트 값도 zone_boosts[]에 대입한다.
  • 코드 라인 38~40에서 restart: 레이블이다. 우선 순위를 초가값(12)으로 한 후 다시 시도한다.
  • 코드 라인 46~67에서 reclaim할 존 인덱스 값으로 classzone_idx를 사용하되, buffer_heads_over_limit가 설정된 경우 가용한 최상위 존을 대입한다.

 

mm/vmscan.c -2/3-

                /*
                 * If the pgdat is imbalanced then ignore boosting and preserve
                 * the watermarks for a later time and restart. Note that the
                 * zone watermarks will be still reset at the end of balancing
                 * on the grounds that the normal reclaim should be enough to
                 * re-evaluate if boosting is required when kswapd next wakes.
                 */
                balanced = pgdat_balanced(pgdat, sc.order, classzone_idx);
                if (!balanced && nr_boost_reclaim) {
                        nr_boost_reclaim = 0;
                        goto restart;
                }

                /*
                 * If boosting is not active then only reclaim if there are no
                 * eligible zones. Note that sc.reclaim_idx is not used as
                 * buffer_heads_over_limit may have adjusted it.
                 */
                if (!nr_boost_reclaim && balanced)
                        goto out;

                /* Limit the priority of boosting to avoid reclaim writeback */
                if (nr_boost_reclaim && sc.priority == DEF_PRIORITY - 2)
                        raise_priority = false;

                /*
                 * Do not writeback or swap pages for boosted reclaim. The
                 * intent is to relieve pressure not issue sub-optimal IO
                 * from reclaim context. If no pages are reclaimed, the
                 * reclaim will be aborted.
                 */
                sc.may_writepage = !laptop_mode && !nr_boost_reclaim;
                sc.may_swap = !nr_boost_reclaim;
                sc.may_shrinkslab = !nr_boost_reclaim;

                /*
                 * Do some background aging of the anon list, to give
                 * pages a chance to be referenced before reclaiming. All
                 * pages are rotated regardless of classzone as this is
                 * about consistent aging.
                 */
                age_active_anon(pgdat, &sc);

                /*
                 * If we're getting trouble reclaiming, start doing writepage
                 * even in laptop mode.
                 */
                if (sc.priority < DEF_PRIORITY - 2)
                        sc.may_writepage = 1;

                /* Call soft limit reclaim before calling shrink_node. */
                sc.nr_scanned = 0;
                nr_soft_scanned = 0;
                nr_soft_reclaimed = mem_cgroup_soft_limit_reclaim(pgdat, sc.order,
                                                sc.gfp_mask, &nr_soft_scanned);
                sc.nr_reclaimed += nr_soft_reclaimed;

                /*
                 * There should be no need to raise the scanning priority if
                 * enough pages are already being scanned that that high
                 * watermark would be met at 100% efficiency.
                 */
                if (kswapd_shrink_node(pgdat, &sc))
                        raise_priority = false;
  • 코드 라인 8~12에서 노드가 밸런스 상태가 아니고, 부스트 중이면 nr_boost_reclaim을 리셋한 후 restart: 레이블로 이동하여 다시 시작한다.
  • 코드 라인 19~20에서 노드가 이미 밸런스 상태이고 부스트 중이 아니면 더이상 페이지 확보를 할 필요 없으므로 out 레이블로 이동한다.
  • 코드 라인 23~24에서 부스트 중에는 priority가 낮은 순위(12~10)는 상관없지만 높은 순위(9~1)부터는 더 이상 우선 순위가 높아지지 않도록 raise_priority에 false를 대입한다.
    • 가능하면 낮은 우선 순위에서는 writeback을 허용하지 않는다.
  • 코드 라인 32~34에서 랩톱(절전 지원) 모드가 아니고 부스트 중이 아니면 may_writepage를 1로 설정하여 writeback을 허용한다. 그리고 부트트 중이 아니면 may_swap 및 may_shrinkslab을 1로 설정하여 swap 및 슬랩 shrink를 지원한다.
  • 코드 라인 42에서 swap이 활성화된 경우 inactive anon이 active anon보다 작을 경우 active 리스트에 대해 shrink를 수행하여 active와 inactive간의 밸런스를 다시 잡아준다.
  • 코드 라인 48~49에서 높은 우선 순위(9~1)에서는 may_writepage를 1로 설정하여 writeback을 허용한다.
  • 코드 라인 52~56에서 노드를 shrink하기 전에 memcg soft limit reclaim을 수행한다. 스캔한 수는 nr_soft_scanned에 대입되고, nr_reclaimed에는 soft reclaim된 페이지 수가 추가된다.
  • 코드 라인 63~64에서 free 페이지가 high 워터마크 기준을 충족할 만큼 노드를 shrink 한다. 만일 shrink가 성공한 경우 순위를 증가시키지 않도록 raise_priority를 false로 설정한다.

 

mm/vmscan.c -3/3-

                /*
                 * If the low watermark is met there is no need for processes
                 * to be throttled on pfmemalloc_wait as they should not be
                 * able to safely make forward progress. Wake them
                 */
                if (waitqueue_active(&pgdat->pfmemalloc_wait) &&
                                allow_direct_reclaim(pgdat))
                        wake_up_all(&pgdat->pfmemalloc_wait);

                /* Check if kswapd should be suspending */
                __fs_reclaim_release();
                ret = try_to_freeze();
                __fs_reclaim_acquire();
                if (ret || kthread_should_stop())
                        break;

                /*
                 * Raise priority if scanning rate is too low or there was no
                 * progress in reclaiming pages
                 */
                nr_reclaimed = sc.nr_reclaimed - nr_reclaimed;
                nr_boost_reclaim -= min(nr_boost_reclaim, nr_reclaimed);

                /*
                 * If reclaim made no progress for a boost, stop reclaim as
                 * IO cannot be queued and it could be an infinite loop in
                 * extreme circumstances.
                 */
                if (nr_boost_reclaim && !nr_reclaimed)
                        break;

                if (raise_priority || !nr_reclaimed)
                        sc.priority--;
        } while (sc.priority >= 1);

        if (!sc.nr_reclaimed)
                pgdat->kswapd_failures++;

out:
        /* If reclaim was boosted, account for the reclaim done in this pass */
        if (boosted) {
                unsigned long flags;

                for (i = 0; i <= classzone_idx; i++) {
                        if (!zone_boosts[i])
                                continue;

                        /* Increments are under the zone lock */
                        zone = pgdat->node_zones + i;
                        spin_lock_irqsave(&zone->lock, flags);
                        zone->watermark_boost -= min(zone->watermark_boost, zone_boosts[i]);
                        spin_unlock_irqrestore(&zone->lock, flags);
                }

                /*
                 * As there is now likely space, wakeup kcompact to defragment
                 * pageblocks.
                 */
                wakeup_kcompactd(pgdat, pageblock_order, classzone_idx);
        }

        snapshot_refaults(NULL, pgdat);
        __fs_reclaim_release();
        psi_memstall_leave(&pflags);
        /*
         * Return the order kswapd stopped reclaiming at as
         * prepare_kswapd_sleep() takes it into account. If another caller
         * entered the allocator slow path while kswapd was awake, order will
         * remain at the higher level.
         */
        return sc.order;
}
  • 코드 라인 6~8에서 페이지 할당 중 메모리가 부족하여 direct reclaim 시도 중 대기하고 있는 태스크들이 pfmemalloc_wait 리스트에 존재하고, 노드가 direct reclaim을 해도 된다고 판단하면 대기 중인 태스크들을 모두 깨운다.
    • allow_direct_reclaim(): normal 존 이하의 free 페이지 합이 min 워터마크를 더한 페이지의 절반보다 큰 경우 true.
  • 코드 라인 12~15에서 freeze 하였다가 깨어났었던 경우 또는 kswapd 스레드 정지 요청이 있는 경우 루프를 빠져나간다.
  • 코드 라인 21~30에서 reclaimed 페이지와 nr_boost_reclaim을 산출한 후 부스트 중이 아니면서 회수된 페이지가 없으면 루프를 벗어난다.
  • 코드 라인 32~34에서 우선 순위를 높이면서 최고 우선 순위까지 루프를 반복한다. 만일 회수된 페이지가 없거나 우선 순위 상승을 원하지 않는 경우에는 우선 순위 증가없이 루프를 반복한다.
  • 코드 라인 36~37에서 루프 완료 후까지 회수된 페이지가 없으면 kswapd_failures 카운터를 증가시킨다.
  • 코드 라인 39~60에서 out: 레이블이다. 처음 시도 시 부스트된 적이 있었으면 kcompactd를 깨운다. 또한 워터마크 부스트 값을 갱신한다.
  • 코드 라인 64에서 메모리 부족으로 인한 현재 태스크의 psi 산출을 종료하는 지점이다.

 

아래 그림은 task A에서 direct 페이지 회수를 진행 중에 pfmemalloc 워터마크 기준 이하로 떨어진 경우 kswapd에 의해 페이지 회수가 될 때까지스로틀링 즉, direct 페이지 회수를 잠시 쉬게 하여 cpu 부하를 줄인다.

 


Kswapd 깨우기

wake_all_kswapds()

mm/page_alloc.c

static void wake_all_kswapds(unsigned int order, gfp_t gfp_mask,
                             const struct alloc_context *ac)
{
        struct zoneref *z;
        struct zone *zone;
        pg_data_t *last_pgdat = NULL;
        enum zone_type high_zoneidx = ac->high_zoneidx;

        for_each_zone_zonelist_nodemask(zone, z, ac->zonelist, high_zoneidx,
                                        ac->nodemask) {
                if (last_pgdat != zone->zone_pgdat)
                        wakeup_kswapd(zone, gfp_mask, order, high_zoneidx);
                last_pgdat = zone->zone_pgdat;
        }
}

alloc context가 가리키는 zonelist 중 관련 노드의 kswpad를 깨운다.

 

wakeup_kswapd()

mm/vmscan.c

/*
 * A zone is low on free memory or too fragmented for high-order memory.  If
 * kswapd should reclaim (direct reclaim is deferred), wake it up for the zone's
 * pgdat.  It will wake up kcompactd after reclaiming memory.  If kswapd reclaim
 * has failed or is not needed, still wake up kcompactd if only compaction is
 * needed.
 */
void wakeup_kswapd(struct zone *zone, gfp_t gfp_flags, int order,
                   enum zone_type classzone_idx)
{
        pg_data_t *pgdat;

        if (!managed_zone(zone))
                return;

        if (!cpuset_zone_allowed(zone, gfp_flags))
                return;
        pgdat = zone->zone_pgdat;
        pgdat->kswapd_classzone_idx = kswapd_classzone_idx(pgdat,
                                                           classzone_idx);
        pgdat->kswapd_order = max(pgdat->kswapd_order, order);
        if (!waitqueue_active(&pgdat->kswapd_wait))
                return;

        /* Hopeless node, leave it to direct reclaim if possible */
        if (pgdat->kswapd_failures >= MAX_RECLAIM_RETRIES ||
            (pgdat_balanced(pgdat, order, classzone_idx) &&
             !pgdat_watermark_boosted(pgdat, classzone_idx))) {
                /*
                 * There may be plenty of free memory available, but it's too
                 * fragmented for high-order allocations.  Wake up kcompactd
                 * and rely on compaction_suitable() to determine if it's
                 * needed.  If it fails, it will defer subsequent attempts to
                 * ratelimit its work.
                 */
                if (!(gfp_flags & __GFP_DIRECT_RECLAIM))
                        wakeup_kcompactd(pgdat, order, classzone_idx);
                return;
        }

        trace_mm_vmscan_wakeup_kswapd(pgdat->node_id, classzone_idx, order,
                                      gfp_flags);
        wake_up_interruptible(&pgdat->kswapd_wait);
}

지정된 zone에서 order 페이지를 할당하려다 메모리가 부족해지면 kswapd 태스크를 깨운다.

  • 코드 라인 6~7에서 유효한 존이 아닌 경우 처리할 페이지가 없으므로 함수를 빠져나간다.
  • 코드 라인 9~10에서 요청한 zone의 노드가 cgroup cpuset을 통해 허가되지 않은 경우 처리를 포기하고 빠져나간다.
  • 코드 라인 11~14에서 kswapd에 존과 order를 지정하여 요청한다.
  • 코드 라인 15~16에서 kswapd가 이미 동작 중이면 함수를 빠져나간다.
  • 코드 라인 19~32에서 다음 조건을 만족하고 direct-reclaim을 허용하지 않는 경우에 한해 kcompactd만 깨우고 함수를 빠져나간다.
    • kswad를 통한 페이지 회수 실패가 MAX_RECLAIM_RETRIES(16)번 이상인 경우
    • 노드가 이미 밸런스 상태이고 부스트 중이 아닌 경우
  • 코드 라인 36에서 kswapd 태스크를 깨운다.

 

current_is_kswapd()

include/linux/swap.h

static inline int current_is_kswapd(void)
{
        return current->flags & PF_KSWAPD;
}

현재 태스크가 kswapd 인 경우 true를 반환한다.

 


kcompactd

kcompactd 초기화

kcompactd_init()

static int __init kcompactd_init(void)
{
        int nid;
        int ret;

        ret = cpuhp_setup_state_nocalls(CPUHP_AP_ONLINE_DYN,
                                        "mm/compaction:online",
                                        kcompactd_cpu_online, NULL);
        if (ret < 0) {
                pr_err("kcompactd: failed to register hotplug callbacks.\n");
                return ret;
        }

        for_each_node_state(nid, N_MEMORY)
                kcompactd_run(nid);
        return 0;
}
subsys_initcall(kcompactd_init)

kcompactd를 사용하기 위해 초기화한다.

  • 코드 라인 6~12에서 cpu가 hot-plug를 통해 CPUHP_AP_ONLINE_DYN 상태로 변경될 때 kcompactd_cpu_online() 함수가 호출될 수 있도록 등록한다.
  • 코드 라인 14~15에서 모든 메모리 노드에 대해 kcompactd를 실행시킨다.

 

kcompactd_run()

mm/compaction.c

/*
 * This kcompactd start function will be called by init and node-hot-add.
 * On node-hot-add, kcompactd will moved to proper cpus if cpus are hot-added.
 */
int kcompactd_run(int nid)
{
        pg_data_t *pgdat = NODE_DATA(nid);
        int ret = 0;

        if (pgdat->kcompactd)
                return 0;

        pgdat->kcompactd = kthread_run(kcompactd, pgdat, "kcompactd%d", nid);
        if (IS_ERR(pgdat->kcompactd)) {
                pr_err("Failed to start kcompactd on node %d\n", nid);
                ret = PTR_ERR(pgdat->kcompactd);
                pgdat->kcompactd = NULL;
        }
        return ret;
}

kcompactd 스레드를 동작시킨다.

  • 코드 라인 3~7에서 @nid 노드의 kcompactd 태스크가 지정되지 않은 경우 0을 반환한다.
  • 코드 라인 9~14에서 kcompactd 스레드를 동작시킨다.

 

kcompactd 동작

kcompactd()

mm/compaction.c

/*
 * The background compaction daemon, started as a kernel thread
 * from the init process.
 */
static int kcompactd(void *p)
{
        pg_data_t *pgdat = (pg_data_t*)p;
        struct task_struct *tsk = current;

        const struct cpumask *cpumask = cpumask_of_node(pgdat->node_id);

        if (!cpumask_empty(cpumask))
                set_cpus_allowed_ptr(tsk, cpumask);

        set_freezable();

        pgdat->kcompactd_max_order = 0;
        pgdat->kcompactd_classzone_idx = pgdat->nr_zones - 1;

        while (!kthread_should_stop()) {
                unsigned long pflags;

                trace_mm_compaction_kcompactd_sleep(pgdat->node_id);
                wait_event_freezable(pgdat->kcompactd_wait,
                                kcompactd_work_requested(pgdat));

                psi_memstall_enter(&pflags);
                kcompactd_do_work(pgdat);
                psi_memstall_leave(&pflags);
        }

        return 0;
}

각 메모리 노드에서 동작되는 kcompactd 스레드는 슬립한 상태에 있다가 kswapd가 페이지 회수를 진행한 후 호출되어 깨어나면 백그라운드에서 compaction을 진행하고 다시 슬립한다.

  • 코드 라인 3~9에서 현재 kcompactd 스레드를 요청 노드에 포함된 cpu들에서만 동작할 수 있도록 cpu 비트마스크를 지정한다.
  • 코드 라인11에서 태스크를 freeze할 수 있도록 PF_NOFREEZE 플래그를 제거한다.
  • 코드 라인 13~14에서 kcompactd의 최대 order와 존을 리셋한다.
  • 코드 라인 16~26에서 종료 요청이 없는 한 계속 루프를 돌며 슬립한 후 외부 요청에 의해 깨어나면 compaction을 수행한다.

 

다음 그림은 kcompactd 스레드가 동작하는 과정을 보여준다.

 

kcompactd_do_work()

mm/compaction.c

static void kcompactd_do_work(pg_data_t *pgdat)
{
        /*
         * With no special task, compact all zones so that a page of requested
         * order is allocatable.
         */
        int zoneid;
        struct zone *zone;
        struct compact_control cc = {
                .order = pgdat->kcompactd_max_order,
                .total_migrate_scanned = 0,
                .total_free_scanned = 0,
                .classzone_idx = pgdat->kcompactd_classzone_idx,
                .mode = MIGRATE_SYNC_LIGHT,
                .ignore_skip_hint = false,
                .gfp_mask = GFP_KERNEL,
        };
        trace_mm_compaction_kcompactd_wake(pgdat->node_id, cc.order,
                                                        cc.classzone_idx);
        count_compact_event(KCOMPACTD_WAKE);

        for (zoneid = 0; zoneid <= cc.classzone_idx; zoneid++) {
                int status;

                zone = &pgdat->node_zones[zoneid];
                if (!populated_zone(zone))
                        continue;

                if (compaction_deferred(zone, cc.order))
                        continue;

                if (compaction_suitable(zone, cc.order, 0, zoneid) !=
                                                        COMPACT_CONTINUE)
                        continue;

                cc.nr_freepages = 0;
                cc.nr_migratepages = 0;
                cc.total_migrate_scanned = 0;
                cc.total_free_scanned = 0;
                cc.zone = zone;
                INIT_LIST_HEAD(&cc.freepages);
                INIT_LIST_HEAD(&cc.migratepages);

                if (kthread_should_stop())
                        return;
                status = compact_zone(zone, &cc);

                if (status == COMPACT_SUCCESS) {
                        compaction_defer_reset(zone, cc.order, false);
                } else if (status == COMPACT_PARTIAL_SKIPPED || status == COMPACT_COMPLETE) {
                        /*
                         * Buddy pages may become stranded on pcps that could
                         * otherwise coalesce on the zone's free area for
                         * order >= cc.order.  This is ratelimited by the
                         * upcoming deferral.
                         */
                        drain_all_pages(zone);

                        /*
                         * We use sync migration mode here, so we defer like
                         * sync direct compaction does.
                         */
                        defer_compaction(zone, cc.order);
                }

                count_compact_events(KCOMPACTD_MIGRATE_SCANNED,
                                     cc.total_migrate_scanned);
                count_compact_events(KCOMPACTD_FREE_SCANNED,
                                     cc.total_free_scanned);

                VM_BUG_ON(!list_empty(&cc.freepages));
                VM_BUG_ON(!list_empty(&cc.migratepages));
        }

        /*
         * Regardless of success, we are done until woken up next. But remember
         * the requested order/classzone_idx in case it was higher/tighter than
         * our current ones
         */
        if (pgdat->kcompactd_max_order <= cc.order)
                pgdat->kcompactd_max_order = 0;
        if (pgdat->kcompactd_classzone_idx >= cc.classzone_idx)
                pgdat->kcompactd_classzone_idx = pgdat->nr_zones - 1;
}

노드에 지정된 kcompactd_classzone_idx 존까지 kcompactd_max_order로 compaction을 수행한다.

  • 코드 라인 9~17에서 kcompactd에서 사용할 compact_control을 다음과 같이 준비한다.
    • .order에 외부에서 요청한 오더를 지정한다.
    • .classzone_idx에 외부에서 요청한 존 인덱스를 지정한다.
    • .mode에 MIGRATE_SYNC_LIGHT를 사용한다.
    • skip 힌트를 사용하도록 한다.
  • 코드 라인 20에서 KCOMPACTD_WAKE 카운터를 증가시킨다.
  • 코드 라인 22~27에서 가장 낮은 존부터 요청한 존까지 순회하며 유효하지 않은 존은 스킵한다.
  • 코드 라인 29~30에서 compaction 유예 조건인 존의 경우 스킵한다.
  • 코드 라인 32~34에서 존이 compaction 하기 적절하지 않은 경우 스킵한다.
  • 코드 라인 36~42에서 compaction을 하기 위해 compaction_control 결과를 담을 멤버들을 초기화한다.
  • 코드 라인 44~45에서 스레드 종료 요청인 경우 함수를 빠져나간다.
  • 코드 라인 46에서 존에 대해 compaction을 수행하고 결과를 알아온다.
  • 코드 라인 48~49에서 만일 compaction이 성공한 경우 유예 카운터를 리셋한다.
  • 코드 라인 50~64에서 만일 compaction이 완료될 때까지 원하는 order가 없는 경우 per-cpu 캐시를 회수하고, 유예 한도를 증가시킨다.
  • 코드 라인 66~69에서 KCOMPACTD_MIGRATE_SCANNED 카운터 및 KCOMPACTD_FREE_SCANNED 카운터를 갱신한다.
  • 코드 라인 80~81에서 진행 order보다 외부 요청 order가 작거나 동일하면 다음에 wakeup 하지 않도록 max_order를 0으로 리셋한다.
  • 코드 라인 82~83에서 진행 존보다 외부 요청 존이 더 크거나 동일하면 다음에 시작할 존을 가장 높은 존으로 리셋한다.

 


Kcompatd 깨우기

wakeup_kcompactd()

mm/compaction.c

void wakeup_kcompactd(pg_data_t *pgdat, int order, int classzone_idx)
{
        if (!order)
                return;

        if (pgdat->kcompactd_max_order < order)
                pgdat->kcompactd_max_order = order;

        if (pgdat->kcompactd_classzone_idx > classzone_idx)
                pgdat->kcompactd_classzone_idx = classzone_idx;

        /*
         * Pairs with implicit barrier in wait_event_freezable()
         * such that wakeups are not missed.
         */
        if (!wq_has_sleeper(&pgdat->kcompactd_wait))
                return;

        if (!kcompactd_node_suitable(pgdat))
                return;

        trace_mm_compaction_wakeup_kcompactd(pgdat->node_id, order,
                                                        classzone_idx);
        wake_up_interruptible(&pgdat->kcompactd_wait);
}

kcompactd 스레드를 깨운다.

  • 코드 라인 3~4에서 order 값이 0인 경우 kcompactd를 깨우지 않고 함수를 빠져나간다.
  • 코드 라인 6~7에서 @order가 kcompactd_max_order 보다 큰 경우 kcompactd_max_order를 갱신한다.
  • 코드 라인 9~10에서 @classzone_idx가 kcompactd_classzone_idx보다 작은 경우 kcompactd_classzone_idx를 갱신한다.
  • 코드 라인 16~17에서 kcompactd가 이미 깨어있으면 함수를 빠져나간다.
  • 코드 라인 19~20에서 compaction을 진행해도 효과가 없을만한 노드의 경우 함수를 빠져나간다.
  • 코드 라인 24에서 kcompactd를 깨운다.

 

kcompactd_node_suitable()

mm/compaction.c

static bool kcompactd_node_suitable(pg_data_t *pgdat)
{
        int zoneid;
        struct zone *zone;
        enum zone_type classzone_idx = pgdat->kcompactd_classzone_idx;

        for (zoneid = 0; zoneid <= classzone_idx; zoneid++) {
                zone = &pgdat->node_zones[zoneid];

                if (!populated_zone(zone))
                        continue;

                if (compaction_suitable(zone, pgdat->kcompactd_max_order, 0,
                                        classzone_idx) == COMPACT_CONTINUE)
                        return true;
        }

        return false;
}

kcompactd를 수행하기 위해 요청한 노드의 가용한 존들에 대해 하나라도 compaction 효과가 있을만한 존이 있는지 여부를 반환한다.

  • 코드 라인 5~11에서 요청한 노드의 kcompactd_classzone_idx 까지 가용한 존들에 대해 순회한다.
  • 코드 라인 13~15에서 순회 중인 존들 중 하나라도 kcompactd_max_order 값을 사용하여 compaction 효과가 있다고 판단하면 true를 반환한다.
  • 코드 라인 18에서 해당 노드의 모든 존들에 대해 compaction 효과를 볼 수 없어 false를 반환한다.

 


기타

swapper_spaces[] 배열

mm/swap_state.c

struct address_space swapper_spaces[MAX_SWAPFILES];

 

swap_aops

mm/swap_state.c

/*                                      
 * swapper_space is a fiction, retained to simplify the path through
 * vmscan's shrink_page_list.
 */
static const struct address_space_operations swap_aops = {
        .writepage      = swap_writepage,
        .set_page_dirty = swap_set_page_dirty,
#ifdef CONFIG_MIGRATION
        .migratepage    = migrate_page,
#endif 
};

 

address_space_operations 구조체

include/linux/fs.h

struct address_space_operations {
        int (*writepage)(struct page *page, struct writeback_control *wbc);
        int (*readpage)(struct file *, struct page *);

        /* Write back some dirty pages from this mapping. */
        int (*writepages)(struct address_space *, struct writeback_control *);

        /* Set a page dirty.  Return true if this dirtied it */
        int (*set_page_dirty)(struct page *page);

        /*
         * Reads in the requested pages. Unlike ->readpage(), this is
         * PURELY used for read-ahead!.
         */
        int (*readpages)(struct file *filp, struct address_space *mapping,
                        struct list_head *pages, unsigned nr_pages);

        int (*write_begin)(struct file *, struct address_space *mapping,
                                loff_t pos, unsigned len, unsigned flags,
                                struct page **pagep, void **fsdata);
        int (*write_end)(struct file *, struct address_space *mapping,
                                loff_t pos, unsigned len, unsigned copied,
                                struct page *page, void *fsdata);

        /* Unfortunately this kludge is needed for FIBMAP. Don't use it */
        sector_t (*bmap)(struct address_space *, sector_t);
        void (*invalidatepage) (struct page *, unsigned int, unsigned int);
        int (*releasepage) (struct page *, gfp_t);
        void (*freepage)(struct page *);
        ssize_t (*direct_IO)(struct kiocb *, struct iov_iter *iter);
        /*
         * migrate the contents of a page to the specified target. If
         * migrate_mode is MIGRATE_ASYNC, it must not block.
         */
        int (*migratepage) (struct address_space *,
                        struct page *, struct page *, enum migrate_mode);
        bool (*isolate_page)(struct page *, isolate_mode_t);
        void (*putback_page)(struct page *);
        int (*launder_page) (struct page *);
        int (*is_partially_uptodate) (struct page *, unsigned long,
                                        unsigned long);
        void (*is_dirty_writeback) (struct page *, bool *, bool *);
        int (*error_remove_page)(struct address_space *, struct page *);

        /* swapfile support */
        int (*swap_activate)(struct swap_info_struct *sis, struct file *file,
                                sector_t *span);
        void (*swap_deactivate)(struct file *file);
};

 

참고