rcu_init()

 

RCU 초기화

rcu_init()

kernel/rcu/tree.c

void __init rcu_init(void)
{
        int cpu;               

        rcu_bootup_announce();
        rcu_init_geometry();
        rcu_init_one(&rcu_bh_state, &rcu_bh_data);
        rcu_init_one(&rcu_sched_state, &rcu_sched_data);
        __rcu_init_preempt();
        open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
        
        /*
         * We don't need protection against CPU-hotplug here because
         * this is called early in boot, before either interrupts
         * or the scheduler are operational.
         */
        cpu_notifier(rcu_cpu_notify, 0);
        pm_notifier(rcu_pm_notify, 0);
        for_each_online_cpu(cpu)
                rcu_cpu_notify(NULL, CPU_UP_PREPARE, (void *)(long)cpu);

        rcu_early_boot_tests();
}

rcu를 사용하기 위해 rcu 관련 구조체들을 초기화하고, cpu 및 pm 상태 변화에 따라 호출되는 각 함수들을 notify chain block에 등록하며 rcu 동작에 필요한 스레드들을 동작시킨다.

  •  rcu_bootup_announce();
    • RCU 설정들이 동작하는지 관련 메시지 로그를 출력한다.
  • rcu_init_geometry();
    • rcu_state 구조체 내부의 rcu_node 들에 대한 트리 기하를 구성하기 위한 설정 값들을 산출한다.
  • rcu_init_one(&rcu_bh_state, &rcu_bh_data);
    • 전역 rcu_bh_state 라는 rcu_state 구조체 및 전역 rcu_bh_data라는 rcu_data 구조체를 초기화하고 구성한다.
  • rcu_init_one(&rcu_sched_state, &rcu_sched_data);
    • 전역 rcu_sched_state 라는 rcu_state 구조체 및 전역 rcu_sched_data라는 rcu_data 구조체를 초기화하고 구성한다.
  • __rcu_init_preempt();
    • CONFIG_PREEMPT_RCU 커널 옵션을 사용하는 경우 전역 rcu_preempt_state 라는 rcu_state 구조체 및 전역 rcu_preempt_data라는 rcu_data 구조체를 초기화하고 구성한다.
  • open_softirq(RCU_SOFTIRQ, rcu_process_callbacks);
    • RCU_SOFTIRQ 벡터에 rcu_process_callbacks 함수를 대입한다.
    • RCU_SOFTIRQ가 호출될 때 마다 전역 rcu_struct_flavors 리스트에 구성된 rcu_state 들을 대상으로  rcu core 처리를 수행한다.
  • cpu_notifier(rcu_cpu_notify, 0);
    • cpu 이벤트에 대해 rcu_cpu_notify() 함수가 호출되도록 notifier block(rcu_cpu_notify_nb)으로 구성한 후 전역 cpu_chain에 추가한다.
  •  pm_notifier(rcu_pm_notify, 0);
    • pm 이벤트에 대해 rcu_pm_notify() 함수가 호출되도록 notifier block(rcu_pm_notify_nb)으로 구성한 후 전역 pm_chain_head에 추가한다.
  • for_each_online_cpu(cpu) rcu_cpu_notify(NULL, CPU_UP_PREPARE, (void *)(long)cpu);
    • 각 cpu에 대해 CPU_UP_PREPARE action을 동작시킨다. 다음 3개의 함수들이 호출된다.
      • rcu_prepare_cpu()
      • rcu_prepare_kthreads()
      • rcu_spawn_all_nocb_kthreads()
  • rcu_early_boot_tests();
    • CONFIG_PROVE_RCU 커널 옵션을 사용한 경우 rcu self test를 진행한다

 

rcu_bootup_announce()

kernel/rcu/tree_plugin.h

/*
 * Tell them what RCU they are running.
 */
static void __init rcu_bootup_announce(void)
{
        pr_info("Preemptible hierarchical RCU implementation.\n");
        rcu_bootup_announce_oddness();
}

어떠한 RCU 설정들이 동작하는지 로그를 출력한다.

 

rcu_bootup_announce_oddness()

kernel/rcu/tree_plugin.h

/*
 * Check the RCU kernel configuration parameters and print informative
 * messages about anything out of the ordinary.  If you like #ifdef, you
 * will love this function.
 */
static void __init rcu_bootup_announce_oddness(void)
{
#ifdef CONFIG_RCU_TRACE
        pr_info("\tRCU debugfs-based tracing is enabled.\n");
#endif
#if (defined(CONFIG_64BIT) && CONFIG_RCU_FANOUT != 64) || (!defined(CONFIG_64BIT) && CONFIG_RCU_FANOUT != 32)
        pr_info("\tCONFIG_RCU_FANOUT set to non-default value of %d\n",
               CONFIG_RCU_FANOUT);
#endif
#ifdef CONFIG_RCU_FANOUT_EXACT
        pr_info("\tHierarchical RCU autobalancing is disabled.\n");
#endif
#ifdef CONFIG_RCU_FAST_NO_HZ
        pr_info("\tRCU dyntick-idle grace-period acceleration is enabled.\n");
#endif
#ifdef CONFIG_PROVE_RCU
        pr_info("\tRCU lockdep checking is enabled.\n");
#endif
#ifdef CONFIG_RCU_TORTURE_TEST_RUNNABLE
        pr_info("\tRCU torture testing starts during boot.\n");
#endif
#if defined(CONFIG_RCU_CPU_STALL_INFO)
        pr_info("\tAdditional per-CPU info printed with stalls.\n");
#endif
#if NUM_RCU_LVL_4 != 0
        pr_info("\tFour-level hierarchy is enabled.\n");
#endif
        if (rcu_fanout_leaf != CONFIG_RCU_FANOUT_LEAF)
                pr_info("\tBoot-time adjustment of leaf fanout to %d.\n", rcu_fanout_leaf);
        if (nr_cpu_ids != NR_CPUS)
                pr_info("\tRCU restricting CPUs from NR_CPUS=%d to nr_cpu_ids=%d.\n", NR_CPUS, nr_cpu_ids);
#ifdef CONFIG_RCU_BOOST
        pr_info("\tRCU kthread priority: %d.\n", kthread_prio);
#endif
}

RCU 설정들에 대해 다음과 같은 로그를 출력한다.

  • CONFIG_RCU_TRACE를 설정한 경우 “RCU debugfs-based tracing is enabled.”
  • CONFIG_RCU_FANOUT 값이 default(32bit=16, 64bit=32) 값과 다른 경우 “CONFIG_RCU_FANOUT set to non-default value of %d”
  • CONFIG_RCU_FANOUT_EXACT가 설정된 경우 “Hierarchical RCU autobalancing is disabled.”
  • CONFIG_RCU_FAST_NO_HZ가 설정된 경우 “RCU dyntick-idle grace-period acceleration is enabled.”
  • CONFIG_PROVE_RCU가 설정된 경우 “RCU lockdep checking is enabled.”
  • CONFIG_RCU_TORTURE_TEST_RUNNABLE가 설정된 경우 “RCU torture testing starts during boot.”
  • CONFIG_RCU_CPU_STALL_INFO가 설정된 경우 “Additional per-CPU info printed with stalls.”
  • NUM_RCU_LVL_4가 설정된 경우 “Four-level hierarchy is enabled.”
  • CONFIG_RCU_FANOUT_LEAF 값이 default 값과 다른 경우 “Boot-time adjustment of leaf fanout to %d.”
  • online cpu와 커널 컴파일 시 설정된 NR_CPUS와 다른 경우 “RCU restricting CPUs from NR_CPUS=%d to nr_cpu_ids=%d.”
  • CONFIG_RCU_BOOST가 설정된 경우 “RCU kthread priority: %d.”

 

rcu_init_geometry()

kernel/rcu/tree.c

/*
 * Compute the rcu_node tree geometry from kernel parameters.  This cannot
 * replace the definitions in tree.h because those are needed to size
 * the ->node array in the rcu_state structure.
 */
static void __init rcu_init_geometry(void)
{
        ulong d;
        int i;
        int j;
        int n = nr_cpu_ids;
        int rcu_capacity[MAX_RCU_LVLS + 1];

        /*
         * Initialize any unspecified boot parameters.
         * The default values of jiffies_till_first_fqs and
         * jiffies_till_next_fqs are set to the RCU_JIFFIES_TILL_FORCE_QS
         * value, which is a function of HZ, then adding one for each
         * RCU_JIFFIES_FQS_DIV CPUs that might be on the system.
         */
        d = RCU_JIFFIES_TILL_FORCE_QS + nr_cpu_ids / RCU_JIFFIES_FQS_DIV;
        if (jiffies_till_first_fqs == ULONG_MAX)
                jiffies_till_first_fqs = d;
        if (jiffies_till_next_fqs == ULONG_MAX)
                jiffies_till_next_fqs = d;

        /* If the compile-time values are accurate, just leave. */
        if (rcu_fanout_leaf == CONFIG_RCU_FANOUT_LEAF &&
            nr_cpu_ids == NR_CPUS)
                return;
        pr_info("RCU: Adjusting geometry for rcu_fanout_leaf=%d, nr_cpu_ids=%d\n",
                rcu_fanout_leaf, nr_cpu_ids);

        /*
         * Compute number of nodes that can be handled an rcu_node tree
         * with the given number of levels.  Setting rcu_capacity[0] makes
         * some of the arithmetic easier.
         */ 
        rcu_capacity[0] = 1;
        rcu_capacity[1] = rcu_fanout_leaf;
        for (i = 2; i <= MAX_RCU_LVLS; i++)
                rcu_capacity[i] = rcu_capacity[i - 1] * CONFIG_RCU_FANOUT;

        /*
         * The boot-time rcu_fanout_leaf parameter is only permitted
         * to increase the leaf-level fanout, not decrease it.  Of course,
         * the leaf-level fanout cannot exceed the number of bits in
         * the rcu_node masks.  Finally, the tree must be able to accommodate
         * the configured number of CPUs.  Complain and fall back to the
         * compile-time values if these limits are exceeded.
         */
        if (rcu_fanout_leaf < CONFIG_RCU_FANOUT_LEAF ||
            rcu_fanout_leaf > sizeof(unsigned long) * 8 ||
            n > rcu_capacity[MAX_RCU_LVLS]) {
                WARN_ON(1);
                return;
        }

        /* Calculate the number of rcu_nodes at each level of the tree. */
        for (i = 1; i <= MAX_RCU_LVLS; i++)
                if (n <= rcu_capacity[i]) {
                        for (j = 0; j <= i; j++)
                                num_rcu_lvl[j] =
                                        DIV_ROUND_UP(n, rcu_capacity[i - j]);
                        rcu_num_lvls = i;
                        for (j = i + 1; j <= MAX_RCU_LVLS; j++)
                                num_rcu_lvl[j] = 0;
                        break;
                }

        /* Calculate the total number of rcu_node structures. */
        rcu_num_nodes = 0;
        for (i = 0; i <= MAX_RCU_LVLS; i++)
                rcu_num_nodes += num_rcu_lvl[i];
        rcu_num_nodes -= n;
}

CONFIG_RCU_FANOUT_LEAF 값이 default 값과 다르거나 nr_cpu_ids가 컴파일 타임에 설정된 NR_CPUS 값과 다른 경우 커널 파라메터들로 부터 rcu_node 트리 기하를 계산한다.

  • 전역 jiffies_till_first_fqs 및 jiffies_till_next_fqs을 산출한다.
  • 전역 rcu_num_lvls 값을 산출한다.
  • 전역 num_rcu_lvl[] 배열에 각 rcu 노드 레벨별로 rcu_node 갯수를 산출한다.
  • 전역 rcu_num_nodes 값을 산출한다.
    • num_rcu_lvl[]을 모두 더한 후 online cpu 수를 제외한 값

 

전역 변수 jiffies_till_first_fqs 및 jiffies_till_next_fqs 에 RCU_JIFFIES_TILL_FORCE_QS 딜레이 값을 디폴트로 대입하되 시스템의 HZ가 256을 넘어가는 케이스 및 online cpu 수가 256개를 초과하는 케이스에 대해 추가로  delay값을 증가하여 설정하다.

  • d = RCU_JIFFIES_TILL_FORCE_QS + nr_cpu_ids / RCU_JIFFIES_FQS_DIV;
    • d 값으로 RCU_JIFFIES_TILL_FORCE_QS를 배정하지만 online cpu 수가 256개 단위를 초과할 때 마다 delay 값을 추가 한다.
    • rpi2: RCU_JIFFES_TILL_FORCE_QS(1) + nr_cpu_ids(4) / RCU_JIFFIES_FQS_DIV(256) = 1
  • if (jiffies_till_first_fqs == ULONG_MAX) jiffies_till_first_fqs = d;
    • 이 함수가 처음 호출되는 경우 jiffies_till_first_fqs 값을 변경한다.
  • if (jiffies_till_next_fqs == ULONG_MAX) jiffies_till_next_fqs = d;
    • 이 함수가 처음 호출되는 경우 jiffies_till_next_fqs 값을 변경한다.
  • if (rcu_fanout_leaf == CONFIG_RCU_FANOUT_LEAF && nr_cpu_ids == NR_CPUS) return;
    • 컴파일 타임에 설정된 값과 실행 시의 값에 변동이 없는 경우 함수를 빠져나간다.
  • pr_info(“RCU: Adjusting geometry for rcu_fanout_leaf=%d, nr_cpu_ids=%d\n”,
    rcu_fanout_leaf, nr_cpu_ids);

    • rcu_fanout_leaf 값이 바뀌거나 실행되는 cpu의 갯수가 컴파일 타임에 설정한 수와 다른 경우 메시지를 출력하고 계속 진행한다.
  • rcu_capacity[0] = 1; rcu_capacity[1] = rcu_fanout_leaf; for (i = 2; i <= MAX_RCU_LVLS; i++) rcu_capacity[i] = rcu_capacity[i – 1] * CONFIG_RCU_FANOUT;
    • rcu_capacity[] 배열에는 각 레벨에서 존재할 수 있는 max rcu_node의 수가 대입된다.
  • for (i = 1; i <= MAX_RCU_LVLS; i++) if (n <= rcu_capacity[i]) {
    • online cpu 수를 처리할 수 있는 레벨이 될 때까지 i를 증가시킨다.
  • for (j = 0; j <= i; j++) num_rcu_lvl[j] = DIV_ROUND_UP(n, rcu_capacity[i – j]);
    • online cpu 수에 맞게 각 레벨에서 필요로 하는 rcu_node의 수를 num_rcu_lvl[]에 대입한다.
  • rcu_num_lvls = i;
    • rcu_node의 tree 레벨을 지정한다.
  • for (j = i + 1; j <= MAX_RCU_LVLS; j++) num_rcu_lvl[j] = 0; break; }
    • num_rcu_lvl[]의 나머지 부분을 0으로 채우고 루프를 빠져나온다.
  • rcu_num_nodes = 0; for (i = 0; i <= MAX_RCU_LVLS; i++) rcu_num_nodes += num_rcu_lvl[i]; rcu_num_nodes -= n;
    • num_rcu_lvl[]을 모두 더한 후 online cpu 수를 빼면 rcu_node의 총 갯수가 산출된다.

 

kernel/rcu/tree.h

#define RCU_JIFFIES_TILL_FORCE_QS (1 + (HZ > 250) + (HZ > 500))
                                        /* For jiffies_till_first_fqs and */
                                        /*  and jiffies_till_next_fqs. */

#define RCU_JIFFIES_FQS_DIV     256     /* Very large systems need more */
                                        /*  delay between bouts of */
                                        /*  quiescent-state forcing. */

 

다음 그림은 jiffies_till_first_fqs 및 jiffies_till_next_fqs를 산출하는 과정을 보여준다.

rcu_init_geometry-1

 

다음 그림은 rcu_capacity[] 배열이 산출된 후의 모습을 보여준다.

rcu_init_geometry-2a

 

다음 그림은 런타임에 nr_cpu_ids의 크기에 대해 각각 최대 값과 샘플 값을 주어 num_rcu_lvl[], rcu_num_nodes 및 rcu_num_lvls를 산출하는 과정을 보여준다.

rcu_init_geometry-3

 

다음은 rpi2에서 알아본 초기 파라메터 값이다.

$ cat /sys/module/rcutree/parameters/jiffies_till_first_fqs
1
$ cat /sys/module/rcutree/parameters/jiffies_till_next_fqs
1
$ cat /sys/module/rcutree/parameters/jiffies_till_sched_qs
5
$ cat /sys/module/rcutree/parameters/rcu_fanout_leaf
16
$ cat /sys/module/rcutree/parameters/qlowmark
100
$ cat /sys/module/rcutree/parameters/qhimark
10000
$ cat /sys/module/rcutree/parameters/blimit
10
$ cat /sys/module/rcutree/parameters/kthread_prio
0

 

빌드 타임 RCU 트리 구성

 

  • 3개로 구성된 rcu_state 구조체 내부에 rcu_node 구조체 배열이 static하게 구성된다.
  • rcu_node 구조체 배열은 NR_CPUS 크기에 따라 1레벨부터 최대 4레벨 까지의 tree 구조를 지원한다.
  • RCU 노드 트리는 최소 1레벨부터 최대 4레벨까지 구성된다.
    • 32bit 시스템
      • 1레벨에서 최대 32개 cpu 지원 가능
      • 2레벨에서 최대 32×32개 cpu 지원 가능
      • 3레벨에서 최대 32x32x32개 cpu 지원 가능
      • 4레벨에서 최대 32x32x32x32개 cpu 지원 가능
    • 64bit 시스템
      • 1레벨에서 최대 64개 cpu 지원 가능
      • 2레벨에서 최대 64×64개 cpu 지원 가능
      • 3레벨에서 최대 64x64x64개 cpu 지원 가능
      • 4레벨에서 최대 64x64x64x64개 cpu 지원 가능
  • leaf 구성
    • 최하단의 leaf는 per-cpu 타입의 rcu_data 구조체가 자리한다.
      • rcu_data 구조 아래에 1:1로 rcu_dynticks 구조체와 연결된다.
  • hotplug cpu를 지원하여 상태가 변화함에 따라 노드 구성이 바뀌게 설계되어 있다.
  • rcu_node의 sub rcu 노드들은 최대 CONFIG_RCU_FANOUT까지 구성된다.
    • 32bit 시스템에서 2~32개까지, 64bit 시스템에서 2~64개까지 설정 가능하다.
    • default: 32bit에서 32, 64bit에서 64
  • 최하단 leaf인 rcu_data 구조체는 최대 rcu_fanout_leaf까지 구성된다.
    • CONFIG_RCU_FANOUT_LEAF
      • 2~RCU_FANOUT까지 설정 가능하다.
      • default: 16

rcutree-1

 

다음 그림은 컴파일 타임에 NR_CPUS 크기에 따라 사용할 레벨이 결정되고 각 레벨별로 rcu 노드 수가 결정되는 것을 보여준다.

rcutree-2

 

다음 그림은 20개의 CPU를 지원하는 설정으로 컴파일 시 구성되는 rcu 노드들의 수를 산출하는 것을 보여준다.

rcutree-3

 

RCU_STATE_INITIALIZER()

kernel/rcu/tree.c

#define RCU_STATE_INITIALIZER(sname, sabbr, cr) \
DEFINE_RCU_TPS(sname) \
struct rcu_state sname##_state = { \
        .level = { &sname##_state.node[0] }, \
        .call = cr, \
        .fqs_state = RCU_GP_IDLE, \
        .gpnum = 0UL - 300UL, \
        .completed = 0UL - 300UL, \
        .orphan_lock = __RAW_SPIN_LOCK_UNLOCKED(&sname##_state.orphan_lock), \
        .orphan_nxttail = &sname##_state.orphan_nxtlist, \
        .orphan_donetail = &sname##_state.orphan_donelist, \
        .barrier_mutex = __MUTEX_INITIALIZER(sname##_state.barrier_mutex), \
        .onoff_mutex = __MUTEX_INITIALIZER(sname##_state.onoff_mutex), \
        .name = RCU_STATE_NAME(sname), \
        .abbr = sabbr, \
}; \
DEFINE_PER_CPU_SHARED_ALIGNED(struct rcu_data, sname##_data)

요청한 이름의 rcu_state  및 rcu_data 구조체를 초기화한다.

  • DEFINE_RCU_TPS()의 경우 CONFIG_TRACING을 사용하지 않는 경우 아무런 동작도 하지 않는다.
  • RCU_STATE_NAME의 경우 __stringify(sname)을 수행하여 문자열이 대입될 수 있도록 한다.
  • 커널 코드에서 다음 3가지의 사용 사례가 있다.
    • RCU_STATE_INITIALIZER(rcu_sched, ‘s’, call_rcu_sched);
    • RCU_STATE_INITIALIZER(rcu_bh, ‘b’, call_rcu_bh);
    • RCU_STATE_INITIALIZER(rcu_preempt, ‘p’, call_rcu);

 

다음 그림은 RCU_STATE_INITIALIZER() 매크로가 수행될 때 요청한 rcu_state 구조체가 초기화되는 과정을 보여준다.

rcu_state_initializer-1

 

다음 그림은 rcu_state 구조체 내부의 rcu_node가 레벨별로 구성된 관계를 보여준다.

  • 4레벨 예제

rcu_state_initializer-2

 

다음 그림은 RCU_STATE_INITIALIZER() 매크로에 의해 사용된 rcu_state 구조체 및 per-cpu로 구성된 rcu_data 구조체들을 보여준다.

rcu_state_initializer-3

 

RCU 구조체 초기화

rcu_init_one()

kernel/rcu/tree.c

/*
 * Helper function for rcu_init() that initializes one rcu_state structure.
 */
static void __init rcu_init_one(struct rcu_state *rsp,
                struct rcu_data __percpu *rda)
{
        static const char * const buf[] = {
                "rcu_node_0",
                "rcu_node_1",
                "rcu_node_2",
                "rcu_node_3" };  /* Match MAX_RCU_LVLS */
        static const char * const fqs[] = {
                "rcu_node_fqs_0",
                "rcu_node_fqs_1",
                "rcu_node_fqs_2",
                "rcu_node_fqs_3" };  /* Match MAX_RCU_LVLS */
        static u8 fl_mask = 0x1;
        int cpustride = 1;
        int i;
        int j;
        struct rcu_node *rnp;

        BUILD_BUG_ON(MAX_RCU_LVLS > ARRAY_SIZE(buf));  /* Fix buf[] init! */

        /* Silence gcc 4.8 warning about array index out of range. */
        if (rcu_num_lvls > RCU_NUM_LVLS)
                panic("rcu_init_one: rcu_num_lvls overflow");

        /* Initialize the level-tracking arrays. */

        for (i = 0; i < rcu_num_lvls; i++)
                rsp->levelcnt[i] = num_rcu_lvl[i];
        for (i = 1; i < rcu_num_lvls; i++)
                rsp->level[i] = rsp->level[i - 1] + rsp->levelcnt[i - 1];
        rcu_init_levelspread(rsp);
        rsp->flavor_mask = fl_mask;
        fl_mask <<= 1;
  • static const char * const buf[] = {
    • rcu 디버깅에 사용되는 문자열로 최대 rcu 레벨을 표시한다.
  • static const char * const fqs[] = {
    • rcu 디버깅에 사용되는 문자열로 최대 rcu 레벨을 표시한다.
  • static u8 fl_mask = 0x1;
    • static 로컬 변수로 이 함수가 호출될 때마다 좌측으로 한 칸씩 쉬프트된다.
  • for (i = 0; i < rcu_num_lvls; i++) rsp->levelcnt[i] = num_rcu_lvl[i];
    • 전역 num_rcu_lvl[]에 저장된 값을 rsp->levelcnt[]에 rcu 레벨 수 만큼 복사한다.
  • for (i = 1; i < rcu_num_lvls; i++) rsp->level[i] = rsp->level[i – 1] + rsp->levelcnt[i – 1];
    • rsp->level[]은 각 레벨이 시작하는 rcu_node를 가리키게 한다.
  • rcu_init_levelspread(rsp);
    • 각 rcu 레벨이 관리하는 sub 노드의 수를 산출한다.
  • rsp->flavor_mask = fl_mask
    • 1을 전역 rcu_struct_flavor 리스트에 등록한 rcu_state 수 만큼 좌측으로 쉬프트 시킨 값을 설정한다.

 

        /* Initialize the elements themselves, starting from the leaves. */

        for (i = rcu_num_lvls - 1; i >= 0; i--) {
                cpustride *= rsp->levelspread[i];
                rnp = rsp->level[i];
                for (j = 0; j < rsp->levelcnt[i]; j++, rnp++) {
                        raw_spin_lock_init(&rnp->lock);
                        lockdep_set_class_and_name(&rnp->lock,
                                                   &rcu_node_class[i], buf[i]);
                        raw_spin_lock_init(&rnp->fqslock);
                        lockdep_set_class_and_name(&rnp->fqslock,
                                                   &rcu_fqs_class[i], fqs[i]);
                        rnp->gpnum = rsp->gpnum;
                        rnp->completed = rsp->completed;
                        rnp->qsmask = 0;
                        rnp->qsmaskinit = 0;
                        rnp->grplo = j * cpustride;
                        rnp->grphi = (j + 1) * cpustride - 1;
                        if (rnp->grphi >= nr_cpu_ids)
                                rnp->grphi = nr_cpu_ids - 1;
                        if (i == 0) {
                                rnp->grpnum = 0;
                                rnp->grpmask = 0;
                                rnp->parent = NULL;
                        } else {
                                rnp->grpnum = j % rsp->levelspread[i - 1];
                                rnp->grpmask = 1UL << rnp->grpnum;
                                rnp->parent = rsp->level[i - 1] +
                                              j / rsp->levelspread[i - 1];
                        }
                        rnp->level = i;
                        INIT_LIST_HEAD(&rnp->blkd_tasks);
                        rcu_init_one_nocb(rnp);
                }
        }

        rsp->rda = rda;
        init_waitqueue_head(&rsp->gp_wq);
        rnp = rsp->level[rcu_num_lvls - 1];
        for_each_possible_cpu(i) {
                while (i > rnp->grphi)
                        rnp++;
                per_cpu_ptr(rsp->rda, i)->mynode = rnp;
                rcu_boot_init_percpu_data(i, rsp);
        }
        list_add(&rsp->flavors, &rcu_struct_flavors);
}
  •  for (i = rcu_num_lvls – 1; i >= 0; i–) {
    • rcu 관리 레벨만큼 역으로 루프를 돈다.
  • cpustride *= rsp->levelspread[i];
    • 하위 노드 갯수가 설정된 levelspread[] 값을 가장 마지막 레벨을 제외하고 역순으로 cpustride에 곱한다.
      • 예) levelspread[] = { 0x10, 0x20, 0x20, 0x10 }
        • cpustride = 0x20, 0x400, 0x4000
  • rnp = rsp->level[i];
    • 현재 rcu 레벨이 가리키는 rcu_node 포인터
  • for (j = 0; j < rsp->levelcnt[i]; j++, rnp++) {
    • 현재 rcu 레벨 수 만큼 루프를 돌며 rcu_node를 증가시킨다.
  • raw_spin_lock_init(&rnp->lock);
    • rcu 노드 spinlock lock를 초기화한다.
  • raw_spin_lock_init(&rnp->fqslock);
    • rcu 노드 spinlock fqslock를 초기화한다.
  • rnp->gpnum = rsp->gpnum; rnp->completed = rsp->completed; rnp->qsmask = 0; rnp->qsmaskinit = 0;
    • gpnum, complted 값은 rcu_state에서 복사하고 qsmask와 qsmaskinit에 0으로 초기화한다.
  • rnp->grplo = j * cpustride; rnp->grphi = (j + 1) * cpustride – 1;
    • 각 노드가 관리하는 cpu 그룹 시작 및 끝 번호를 대입한다.
      • 예) nr_cpu_ids=0x2000일때 최상위 rcu_node
        • grplo=0x0, grphi=0x1fff
  • if (rnp->grphi >= nr_cpu_ids) rnp->grphi = nr_cpu_ids – 1;
    • 만일 노드의 grphi 값이 nr_cpu_ids와 동일하거나 큰 경우 nr_cpu_ids 값보다 1 작게 교정한다.
  • if (i == 0) { rnp->grpnum = 0; rnp->grpmask = 0; rnp->parent = NULL;
    • 최상위 rcu 노드의 경우 grpnum, grpmask, parent를 0으로 초기화한다.
  • } else { rnp->grpnum = j % rsp->levelspread[i – 1]; rnp->grpmask = 1UL << rnp->grpnum; rnp->parent = rsp->level[i – 1] + j / rsp->levelspread[i – 1]; }
    • 최상위 rcu 노드가 아닌 경우 grpnum, grpmask, parent를 산출한다.
      • grpnum
        • 부모가 동일한 노드들 중 가장 좌측부터 항상 0부터 시작하여 1씩 증가된다.
      • grpmask
        • 1을 grpnum만큼 쉬프트하여 대입한다.
        • 1, 2, 4, 8, …
      • parent
        • 부모 노드를 가리킨다.
  • rnp->level = i;
    • rcu 노드의 레벨을 대입한다.
      • 0 ~ 최대 3
  • INIT_LIST_HEAD(&rnp->blkd_tasks);
    • 노드의 blkd_tasks 리스트를 초기화한다.
  • rcu_init_one_nocb(rnp);
    • CONFIG_RCU_NOCB_CPU 커널 옵션이 사용되는 경우 nocb_gp_wq[]에 있는 대기큐 두 개를 초기화한다.
  • rsp->rda = rda;
    • rcu_state 노드의 rda는 인수로 건네받은 percpu 구조체인 rcu_data를 지정한다.
  • init_waitqueue_head(&rsp->gp_wq);
    • 대기 큐를 초기화한다.
  • rnp = rsp->level[rcu_num_lvls – 1];
    • 최하위 레벨의 첫 rcu 노드를 가리키게 한다.
  • for_each_possible_cpu(i) { while (i > rnp->grphi) rnp++;
    • cpu 번호가 현재 노드의 grphi를 초과하는 경우 해당 노드가 처리하지 않아 다음 노드를 가리키게 한다.
  • per_cpu_ptr(rsp->rda, i)->mynode = rnp;
    • 현재 cpu의 rcu_data 구조체의 mynode가 현재 rcu_node를 가리키게 한다.
  • rcu_boot_init_percpu_data(i, rsp);
    • 현재 cpu에 대한 rcu_data 구조체를 초기화한다.
  • list_add(&rsp->flavors, &rcu_struct_flavors);
    • 마지막으로 요청한 rcu_state 구조체를 전역 rcu_struct_flavors 리스트에 추가한다.

 

다음 그림은 rcu_init_one() 함수를 호출하여 rcu_state, rcu_node 및 rcu_data 구조체들이 초기화되는 과정을 보여준다.

rcu_init_one-1

 

다음 그림은 전역 rcu_struct_flavors 리스트에 추가된 rcu_state 들을 보여준다.

rcu_init_one-2

 

다음 그림은 rcu_node의 grplo 및 grphi를 산출하는 과정을 보여준다.

rcu_init_one-3

 

다음 그림은 rcu_node의 grpnum, grpmask 및 level을 산출하는 과정을 보여준다.

rcu_init_one-4

 

다음 그림은 3단계로 구성된 rcu_node 구성을 트리 구조로 보여준 사례이다.

rcu_init_one-5

 

rcu_init_levelspread()

kernel/rcu/tree.c

/*
 * Compute the per-level fanout, either using the exact fanout specified
 * or balancing the tree, depending on CONFIG_RCU_FANOUT_EXACT.
 */
#ifdef CONFIG_RCU_FANOUT_EXACT
static void __init rcu_init_levelspread(struct rcu_state *rsp)
{
        int i;

        rsp->levelspread[rcu_num_lvls - 1] = rcu_fanout_leaf;
        for (i = rcu_num_lvls - 2; i >= 0; i--)
                rsp->levelspread[i] = CONFIG_RCU_FANOUT;
}
#else /* #ifdef CONFIG_RCU_FANOUT_EXACT */
static void __init rcu_init_levelspread(struct rcu_state *rsp)
{
        int ccur;
        int cprv;
        int i;

        cprv = nr_cpu_ids;
        for (i = rcu_num_lvls - 1; i >= 0; i--) {
                ccur = rsp->levelcnt[i];
                rsp->levelspread[i] = (cprv + ccur - 1) / ccur;
                cprv = ccur;
        }
}
#endif /* #else #ifdef CONFIG_RCU_FANOUT_EXACT */

각 rcu 레벨이 관리하는 sub 노드의 수를 산출한다.

  • CONFIG_RCU_FANOUT_EXACT 커널 옵션 사용 유무에 따라
    • 사용하는 경우 최하위 노드는 rcu_fanout_leaf(default: 0x10)개를 관리하고, 그 상위 노드들은 CONFIG_RCU_FANOUT 개를 관리한다.
    • 사용하지 않는 경우 online cpu 수에 맞게 각 레벨의 노드가 관리하는 sub 노드 수가 필요한 만큼 설정된다.

 

다음 그림은 online cpu 수에 따라 levelspread[] 배열 값이 산출되는 모습을 보여준다.

  • 좌측 4개 레벨은 max online cpu 수로 산출하였고, 우측 4개 레벨은 임의의 online cpu 수로 산출하였다.

rcu_init_levelspread-1

 

rcu_init_one_nocb()

kernel/rcu/tree_plugin.h

static void rcu_init_one_nocb(struct rcu_node *rnp)
{
        init_waitqueue_head(&rnp->nocb_gp_wq[0]);
        init_waitqueue_head(&rnp->nocb_gp_wq[1]);
}

CONFIG_RCU_NOCB_CPU 커널 옵션이 사용되는 경우 nocb_gp_wq[]에 있는 대기큐 두 개를 초기화한다.

 

rcu_boot_init_percpu_data()

kernel/rcu/tree.c

/*
 * Do boot-time initialization of a CPU's per-CPU RCU data.
 */
static void __init
rcu_boot_init_percpu_data(int cpu, struct rcu_state *rsp)
{
        unsigned long flags;
        struct rcu_data *rdp = per_cpu_ptr(rsp->rda, cpu);
        struct rcu_node *rnp = rcu_get_root(rsp);

        /* Set up local state, ensuring consistent view of global state. */
        raw_spin_lock_irqsave(&rnp->lock, flags);
        rdp->grpmask = 1UL << (cpu - rdp->mynode->grplo);
        rdp->dynticks = &per_cpu(rcu_dynticks, cpu);
        WARN_ON_ONCE(rdp->dynticks->dynticks_nesting != DYNTICK_TASK_EXIT_IDLE);
        WARN_ON_ONCE(atomic_read(&rdp->dynticks->dynticks) != 1);
        rdp->cpu = cpu;
        rdp->rsp = rsp;
        rcu_boot_init_nocb_percpu_data(rdp);
        raw_spin_unlock_irqrestore(&rnp->lock, flags);
}

cpu별로 구성되는 rcu_data 구조체의 멤버를 부트타임에 모두 초기화한다.

  • rdp->grpmask
    • 동일한 상위노드를 바라보는 경우 가장 좌측을 1부터 2배 단위로 증가한다.
      • 1, 2, 4, 8, …
  • rdp->dynticks
    • 전역 per-cpu 구조체인 rcu_dynticks에서 cpu에 해당하는 구조체 위치를 가리키게한다.
  • rdp->cpu
    • 담당 cpu 번호가 담긴다.
  • rdp->rsp
    • 담당 rcu_state를 가리키는 포인터가 대입된다.
  • rdp->nocb_tail
    • rdp->nocb_head를 가리킨다.
  • rdp->nocb_wq
    • nocb 대기큐
  • rdp->nocb_follower_tail
    • rdp->nocb_follower_head를 가리킨다.

 

rcu_cpu_notify()

kernel/rcu/tree.c

/*
 * Handle CPU online/offline notification events.
 */
static int rcu_cpu_notify(struct notifier_block *self,
                                    unsigned long action, void *hcpu)
{
        long cpu = (long)hcpu; 
        struct rcu_data *rdp = per_cpu_ptr(rcu_state_p->rda, cpu);
        struct rcu_node *rnp = rdp->mynode;
        struct rcu_state *rsp;

        trace_rcu_utilization(TPS("Start CPU hotplug"));
        switch (action) {
        case CPU_UP_PREPARE:
        case CPU_UP_PREPARE_FROZEN:
                rcu_prepare_cpu(cpu);
                rcu_prepare_kthreads(cpu);
                rcu_spawn_all_nocb_kthreads(cpu);
                break;
        case CPU_ONLINE:
        case CPU_DOWN_FAILED:
                rcu_boost_kthread_setaffinity(rnp, -1);
                break;
        case CPU_DOWN_PREPARE:
                rcu_boost_kthread_setaffinity(rnp, cpu);
                break;
        case CPU_DYING:
        case CPU_DYING_FROZEN:
                for_each_rcu_flavor(rsp)
                        rcu_cleanup_dying_cpu(rsp);
                break;
        case CPU_DEAD:
        case CPU_DEAD_FROZEN:
        case CPU_UP_CANCELED:
        case CPU_UP_CANCELED_FROZEN:
                for_each_rcu_flavor(rsp) {
                        rcu_cleanup_dead_cpu(cpu, rsp);
                        do_nocb_deferred_wakeup(per_cpu_ptr(rsp->rda, cpu));
                }
                break;
        default:
                break;
        }
        trace_rcu_utilization(TPS("End CPU hotplug"));
        return NOTIFY_OK;
}

cpu 상태 변화에 따른 통지를 받았을 때 action에 따라 처리할 함수를 호출한다.

 

rcu_prepare_cpu()

kernel/rcu/tree.c

static void rcu_prepare_cpu(int cpu)
{
        struct rcu_state *rsp;

        for_each_rcu_flavor(rsp)
                rcu_init_percpu_data(cpu, rsp);
}

전역 rcu_struct_flavor 리스트에 구성된 rcu_state가 관리하는 rcu_data 구조체에 대해 요청 cpu에 대해 멤버를 실행타임에 초기화한다.

  • rcu_init_percpu_data()
    • (생략)

 

rcu_prepare_kthreads()

kernel/rcu/tree_plugin.h

static void rcu_prepare_kthreads(int cpu)
{
        struct rcu_data *rdp = per_cpu_ptr(rcu_state_p->rda, cpu);
        struct rcu_node *rnp = rdp->mynode;

        /* Fire up the incoming CPU's kthread and leaf rcu_node kthread. */
        if (rcu_scheduler_fully_active)
                (void)rcu_spawn_one_boost_kthread(rcu_state_p, rnp);
}

CONFIG_RCU_BOOST 커널 옵션을 사용한 경우에만 동작되며, 전역 rcu_scheduler_fully_active가 true인 경우에만 rcu_spawn_one_boost_kthread()를 호출하여 rcu_boost_kthread라는 이름의 스레드를 생성하여 동작시킨다.

 

rcu_spawn_all_nocb_kthreads()

kernel/rcu/tree_plugin.h

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

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

CONFIG_RCU_NOCB_CPU 커널 옵션을 사용한 경우에만 동작되며, 전역 rcu_scheduler_fully_active가 true인 경우에만 전역 rcu_struct_flavors 리스트에 연결된 rcu_state들에 대해 rcu_nocb_kthread라는 이름의 스레드를 생성하여 동작시킨다.

 

rcu_early_boot_tests()

kernel/rcu/update.c

void rcu_early_boot_tests(void)
{               
        pr_info("Running RCU self tests\n");

        if (rcu_self_test)
                early_boot_test_call_rcu();
        if (rcu_self_test_bh)
                early_boot_test_call_rcu_bh();
        if (rcu_self_test_sched)
                early_boot_test_call_rcu_sched();
}

CONFIG_PROVE_RCU 커널 옵션을 사용한 경우 동작되며 다음 3개 케이스에 대해 rcu self test를 진행한다.

  • /sys/module/rcupdate/parameters/rcu_self_test가 1로 설정된 경우에 early_boot_test_call_rcu() 함수를 호출
  • /sys/module/rcupdate/parameters/rcu_self_test_bh가 1로 설정된 경우에 early_boot_test_call_rcu_bh() 함수를 호출
  • /sys/module/rcupdate/parameters/rcu_self_test_sched가 1로 설정된 경우에 early_boot_test_call_rcu_sched() 함수를 호출

 

참고

답글 남기기

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