RCU-3——经典(可抢占)RCU代码分析

基于 Linux-5.10

一、相关数据结构

1. struct rcu_state

rcu_state 用于描述RCU全局状态。

struct rcu_state {
    struct rcu_node node[NUM_RCU_NODES]; /* Hierarchy. */
    struct rcu_node *level[RCU_NUM_LVLS + 1]; /* Hierarchy levels (+1 to shut bogus gcc warning) */
    int ncpus; /* # CPUs seen so far. */

    /* The following fields are guarded by the root rcu_node's lock. */

    u8    boost ____cacheline_internodealigned_in_smp; /* Subject to priority boost. */
    unsigned long gp_seq;  /* Grace-period sequence #. */
     unsigned long gp_max; /* Maximum GP duration in jiffies. */
    struct task_struct *gp_kthread; /* Task for grace periods. */
    struct swait_queue_head gp_wq; /* Where GP task waits. */
    short gp_flags;  /* Commands for GP task. */
    short gp_state; /* GP kthread sleep state. */
    unsigned long gp_wake_time; /* Last GP kthread wake. */
    unsigned long gp_wake_seq; /* ->gp_seq at ^^^. */

    /* End of fields guarded by root rcu_node's lock. */

    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 barrier_sequence; /* ++ at start and end of rcu_barrier(). */
    /* End of fields guarded by barrier_mutex. */

    struct mutex exp_mutex; /* Serialize expedited GP. */
    struct mutex exp_wake_mutex; /* Serialize wakeup. */
    unsigned long expedited_sequence; /* Take a ticket. */
    atomic_t expedited_need_qs; /* # CPUs left to check in. */
    struct swait_queue_head expedited_wq; /* Wait for check-ins. */
    int ncpus_snap; /* # CPUs seen last time. */
    u8 cbovld;  /* Callback overload now? */
    u8 cbovldnext; /* ^ ^  next time? */

    unsigned long jiffies_force_qs; /* Time at which to invoke force_quiescent_state(). */
    unsigned long jiffies_kick_kthreads;  /* Time at which to kick kthreads, if configured. */
    unsigned long n_force_qs; /* Number of calls to force_quiescent_state(). */
    unsigned long gp_start; /* Time at which GP started, but in jiffies. */
    unsigned long gp_end; /* Time last GP ended, again in jiffies. */
    unsigned long gp_activity; /* Time of last GP kthread activity in jiffies. */
    unsigned long gp_req_activity; /* Time of last GP request 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. */
    const char *name;  /* Name of structure. */
    char abbr;  /* Abbreviated name. */

    raw_spinlock_t ofl_lock ____cacheline_internodealigned_in_smp; /* Synchronize offline with GP pre-initialization. */
};

成员说明：

name: 若使能了抢占类型的rcu就是"rcu_preempt".
node[NUM_RCU_NODES]: 定义了所有树节点，存放系统中所有 rcu_node 实体。node[0] 是根节点，见 rcu_get_root(). 对于8核但是 NR_CPUS 却是32的平台，NUM_RCU_NODES=3。
level[RCU_NUM_LVLS + 1]: 2+1=3个元素的数组，指向每层的第一个 rcu_node 实例。
ncpus: 总的处理器数量。
gp_seq: 当前宽限期编号。低2bit表示状态，若不为0表示GP正在处理，见 rcu_gp_in_progress() 中判断。此三个结构都有这个成员。
gp_max: 目前系统上经历过的最长的宽限期的时间，单位jiffies，宽限期线程中取 max(gp_end-gp_start) 的值。
gp_kthread: 指向宽限期内核线程，函数体为 rcu_gp_kthread。每种都RCU创建了一个宽限期线程，专门负责启动新的宽限期和结束当前宽限期。
gp_wq: 宽限期线程的等待队列。在 rcu_gp_kthread_wake() 中会从这个队列上得到宽限期线程然后唤醒它。
gp_flags：用来向宽限期线程传递命令。其中标志 RCU_GP_FLAG_INIT 表示需要启动新的宽限期，RCU_GP_FLAG_FQS 表示需要强制静止状态。
gp_state: 宽限期线程的睡眠状态。
RCU_GP_IDLE: 没有宽限期，
RCU_GP_WAIT_GPS: 等待宽限期的开始，
RCU_GP_DONE_GPS: 停止等待宽限期开始，
RCU_GP_WAIT_FQS: 等待强制静止状态时刻，
RCU_GP_DOING_FQS: 停止等待强制静止状态时刻，
RCU_GP_CLEANUP: 宽限期清理开始，
RCU_GP_CLEANED: 宽限期清理结束。
cbovld: 当前系统的 callback 是否堆积过多。
gp_start: 宽限期开始时间，单位jiffies，在宽限期线程的 record_gp_stall_check_time() 中唯一设置。
gp_end: 宽限期结束时间，单位jiffies，在宽限期线程的 rcu_gp_cleanup() 函数中唯一设置。
gp_activity: 在宽限期线程 rcu_gp_kthread() 执行过程中的多个事件中都更新了其值，比如宽限期更新、强制静态、宽限期清除等。
gp_wake_time: 宽限期线程被唤醒时间。所有处理器都经历了静态后唤醒宽限期线程结束当前宽限期时设置为jiffies，见 rcu_gp_kthread_wake().
gp_wake_seq: 宽限期线程被唤醒时记录当前宽限期编号。rcu_gp_kthread_wake() 中唯一赋值。

2. struct rcu_node

rcu_node 用于描述一个处理器分组的RCU状态。其 parent 成员指向上一层 rcu_node 实例，每个处理器的 rcu_data 实例的 mynode 成员指向叶子 rcu_node 节点。

struct rcu_node {
    /* 根 rcu_node 的锁保护了一些 rcu_state 字段以及以下内容。 */
    raw_spinlock_t __private lock;
    /* 跟踪  rsp->gp_seq */
    unsigned long gp_seq;
    /* 跟踪最远的未来 GP 请求 */
    unsigned long gp_seq_needed;
    /* 为此节点完成的所有 QSes */
    unsigned long completedqs;
    /*
     * 需要切换以使当前宽限期继续进行的 CPU 或组。 在叶子 rcu_node 中，
     * 每一位对应一个 rcu_data 结构，否则，每一位对应一个 child rcu_node 结构。
     */
    unsigned long qsmask;
    /* GP 初始化时offline的 CPU 的掩码。 */
    unsigned long rcu_gp_init_mask;
    /* qsmask 的每个 GP 初始值。 在每个宽限期开始时从 ->qsmaskinitnext 初始化。 */
    unsigned long qsmaskinit;
    /* 下一个宽限期的online CPU。 */
    unsigned long qsmaskinitnext;
    /* 需要签入以允许当前加速 GP 完成的 CPU 或组。 */
    unsigned long expmask;
    /* expmask 的每 GP 的初始值。在每个加速 GP 的开头从 ->expmaskinitnext 初始化。 */
    unsigned long expmaskinit;
    /* 下一个加速 GP 的online CPU。 任何曾经在线的 CPU 都将设置其bit位。 */
    unsigned long expmaskinitnext;
    /* 正在经历过载回调的CPU */
    unsigned long cbovldmask;
    /* 功能齐全的 CPU */
    unsigned long ffmask;
    /* 应用于父 qsmask 的掩码。只会在此掩码中设置一个bit位 */
    unsigned long grpmask;
    /* 该分组的CPU最小编号 */
    int    grplo;
    /* 该分组的CPU最大编号 */
    int    grphi;
    /* 该分组在上一层分组里的编号 */
    u8    grpnum;
    /* 在树中的层级，Root为0 */
    u8    level;
    /* 在offline向上传播到 rcu_node 树之前，是否需要等待阻塞的任务退出 RCU 读端临界区？ */
    bool    wait_blkd_tasks;
    /* 只有一个父节点，是单向构成树 */
    struct rcu_node *parent;
    /* 在 RCU 读取端临界区中阻塞的任务。 任务被放置在这个列表的头部，旧的在尾部。 */
    struct list_head blkd_tasks;
    /* 指向阻塞当前宽限期的第一个任务的指针，如果没有这样的任务，则为 NULL。blkd_tasks 挂在这个链表上 */
    struct list_head *gp_tasks;
    /*
     * 指向阻塞当前加速宽限期的第一个任务的指针，如果没有这样的任务，则为 NULL。 
     * 如果当前没有加速的宽限期，那么就不可能有任何这样的任务。
     */
    struct list_head *exp_tasks;
    /*
     * 指向需要提升优先级的第一个任务的指针，如果此 rcu_node 结构不需要提升优先级，
     * 则为 NULL。 如果在这个 rcu_node 结构上没有任务排队阻塞当前的宽限期，那么就
     * 不会有这样的任务。 
     */
    struct list_head *boost_tasks;
    /* 仅用于利用rt_mutex提高优先级，不用作锁。 */
    struct rt_mutex boost_mtx;
    /* 何时开始boosting(jiffies) */
    unsigned long boost_time;
    /* 负责(关注？)此 rcu_node 结构的优先级提升的 kthread */
    struct task_struct *boost_kthread_task;
    /* 用于跟踪的 boost_kthread_task 的状态。 */
    unsigned int boost_kthread_status;
#ifdef CONFIG_RCU_NOCB_CPU
    /* rcu_nocb_kthread() 等待 GP 的地方。 */
    struct swait_queue_head nocb_gp_wq[2];
#endif /* #ifdef CONFIG_RCU_NOCB_CPU */
    raw_spinlock_t fqslock ____cacheline_internodealigned_in_smp;

    spinlock_t exp_lock ____cacheline_internodealigned_in_smp;
    unsigned long exp_seq_rq;
    wait_queue_head_t exp_wq[4];
    struct rcu_exp_work rew;
    bool exp_need_flush;    /* Need to flush workitem? */
} ____cacheline_internodealigned_in_smp;

主要成员：

lock: 保护此node的spin lock。
gp_seq: 本节点当前宽限期编号，最后2bit表示状态。tree中的三个结构各有一个这个成员。
completedqs: 当前node已经度过的所有QS，且 gp_tasks 指针为NULL的次数。
qsmask: 是静止状态位图，用来记录哪些成员经历了正常宽限期的静止状态。若某个bit位为1则表示该成员没有经历静止状态。
qsmaskinit: 是每个正常宽限期开始的时候静止状态位图的初始值。从 qsmaskinitnext 中获取，用来赋给 qsmask。
qsmaskinitnext: 是下一个正常宽限期开始时的静止状态位图的初始值，和处理器热插拔有关，可能有些cpu下线了。
expmask: 用来记录哪些成员经历了加速宽限期的静止状态的位图。
expmaskinit: 是每个加速宽限期开始的时候静止状态位图的初始值。
expmaskinitnext: 下一个加速宽限期开始的时候静止状态位图的初始值。
grpmask: 是该分组在上一层分组中的位图中的位掩码，表示此node对应父node的qsmask的哪个bit。
grplo: 属于该分组的处理器最小编号。
grphi: 属于该分组的处理器最大编号。
grpnum: 是该分组在上一层分组中的编号。
level: 是本节点在树中的层次编号，根是0。rcu_is_leaf_node(rnp) 使用此成员来判断是不是叶子节点。
parent: 指向上一分层，即指向父node。
blkd_tasks: 对于可抢占rcu，任务在读临界区被抢占后，通过其 t->rcu_node_entry 挂在这个链表上。如果宽限期正在等待这个链表中的元素，它还会等待所有后续元素。
因此，将任务添加到链表表的尾部会阻止已经在等待其中一个元素的任何宽限期。相反，将任务添加到列表的头部则不会阻止任何已经在等待其中一个元素的宽限期。见 rcu_preempt_ctxt_queue() 的备注。
gp_tasks: 指示正常宽限期正在等待哪个任务，指向的是 t->rcu_node_entry，若没有则为NULL。见 rcu_preempt_ctxt_queue() 的备注。也即指向 blkd_tasks 中阻塞当前宽限期的第一个进程，当前node度过qs时，
此成员必须为NULL。
exp_tasks: 指针指示加速宽限期正在等待哪个任务，指向的是 t->rcu_node_entry，如果没有等待的任务则为 NULL。见 rcu_preempt_ctxt_queue() 的备注。

3. struct rcu_data

rcu_data 用于描述一个处理器的RCU状态，每个处理器对应一个 rcu_data 实例。

/* Per-CPU data for read-copy update. */
struct rcu_data {
    /* 1）静态和宽限期处理： */
    unsigned long    gp_seq; /* Track rsp->gp_seq counter. rsp 是指向 rcu_state的指针 */
    unsigned long    gp_seq_needed;  /* Track furthest future GP request. */
    union rcu_noqs    cpu_no_qs;  /* No QSes yet for this CPU. */

    /* RCU需要本CPU上报QS状态 */
    bool        core_needs_qs;  /* Core waits for quiesc state. */
    bool        beenonline;  /* CPU online at least once. */
    bool        gpwrap; /* Possible ->gp_seq wrap. */
    bool        exp_deferred_qs;  /* This CPU awaiting a deferred QS? */
    bool        cpu_started; /* RCU watching this onlining CPU. */
    struct rcu_node *mynode; /* This CPU's leaf of hierarchy */
    unsigned long grpmask;    /* 应用于叶qsmask的mask */
    /* 这个 CPU 在它知道的最后一个宽限期期间和之后处理的调度时钟滴答数。 */
    unsigned long    ticks_this_gp;
    struct irq_work defer_qs_iw; /* Obtain later scheduler attention. */
    bool defer_qs_iw_pending;  /* Scheduler attention pending? */
    struct work_struct strict_work;  /* Schedule readers for strict GPs. */

    /* 2) batch handling */
    /* 分段回调链表，用于存放call_rcu注册的延后执行的回调函数，不同的回调等待不同的宽限期 */
    struct rcu_segcblist cblist;
    long        qlen_last_fqs_check; /* qlen at last check for QS forcing */
    unsigned long    n_cbs_invoked;    /* # callbacks invoked since boot. */
    unsigned long    n_force_qs_snap; /* did other CPU force QS recently? */
    long        blimit;        /* 已处理批次的上限 */

    /* 3) dynticks 接口。 */
    int dynticks_snap;        /* Per-GP tracking for dynticks. */
    long dynticks_nesting;        /* Track process nesting level. */
    long dynticks_nmi_nesting;    /* Track irq/NMI nesting level. */
    atomic_t dynticks;        /* Even value for idle, else odd. */
    bool rcu_need_heavy_qs;        /* GP old, so heavy quiescent state! */
    bool rcu_urgent_qs;        /* GP old need light quiescent state. */
    bool rcu_forced_tick;        /* Forced tick to provide QS. */
    bool rcu_forced_tick_exp;    /* ... provide QS to expedited GP. */
#ifdef CONFIG_RCU_FAST_NO_HZ //默认使能
    unsigned long last_accelerate;    /* Last jiffy CBs were accelerated. */
    unsigned long last_advance_all;    /* Last jiffy CBs were all advanced. */
    int tick_nohz_enabled_snap;    /* Previously seen value from sysfs. */
#endif /* #ifdef CONFIG_RCU_FAST_NO_HZ */

    /* 4) rcu_barrier(), OOM callbacks, and expediting. */
    struct rcu_head barrier_head;
    int exp_dynticks_snap;        /* Double-check need for IPI. */

    /* 5) Callback offloading. */
#ifdef CONFIG_RCU_NOCB_CPU //默认使能
    struct swait_queue_head nocb_cb_wq; /* For nocb kthreads to sleep on. */
    struct task_struct *nocb_gp_kthread;
    raw_spinlock_t nocb_lock;    /* Guard following pair of fields. */
    atomic_t nocb_lock_contended;    /* Contention experienced. */
    int nocb_defer_wakeup;        /* Defer wakeup of nocb_kthread. */
    struct timer_list nocb_timer;    /* Enforce finite deferral. */
    unsigned long nocb_gp_adv_time;    /* Last call_rcu() CB adv (jiffies). */

    /* 以下字段由 call_rcu 使用，因此拥有缓存行 */
    raw_spinlock_t nocb_bypass_lock ____cacheline_internodealigned_in_smp;
    struct rcu_cblist nocb_bypass;    /* Lock-contention-bypass CB list. */
    unsigned long nocb_bypass_first; /* Time (jiffies) of first enqueue. */
    unsigned long nocb_nobypass_last; /* Last ->cblist enqueue (jiffies). */
    int nocb_nobypass_count;    /* # ->cblist enqueues at ^^^ time. */

    /* 以下字段由 GP kthread 使用，因此拥有缓存行 */
    raw_spinlock_t nocb_gp_lock ____cacheline_internodealigned_in_smp;
    struct timer_list nocb_bypass_timer; /* Force nocb_bypass flush. */
    u8 nocb_gp_sleep;        /* Is the nocb GP thread asleep? */
    u8 nocb_gp_bypass;        /* Found a bypass on last scan? */
    u8 nocb_gp_gp;            /* GP to wait for on last scan? */
    unsigned long nocb_gp_seq;    /* If so, ->gp_seq to wait for. */
    unsigned long nocb_gp_loops;    /* # passes through wait code. */
    struct swait_queue_head nocb_gp_wq; /* For nocb kthreads to sleep on. */
    bool nocb_cb_sleep;        /* Is the nocb CB thread asleep? */
    struct task_struct *nocb_cb_kthread;
    struct rcu_data *nocb_next_cb_rdp; /* Next rcu_data in wakeup chain. */

    /* 以下字段由 CB kthread 使用，因此是新的缓存行 */
    struct rcu_data *nocb_gp_rdp ____cacheline_internodealigned_in_smp; /* GP rdp takes GP-end wakeups. */
#endif /* #ifdef CONFIG_RCU_NOCB_CPU */

    /* 6) RCU 优先级提升。 */
    struct task_struct *rcu_cpu_kthread_task; /* rcuc per-CPU kthread or NULL. */
    unsigned int rcu_cpu_kthread_status;
    char rcu_cpu_has_work;

    /* 7) 诊断数据，包括 RCU CPU stall警告。 */
    /* softirq 活动的快照。 ->rcu_iw* 字段受叶 rcu_node ->lock 保护。 */
    unsigned int softirq_snap;
    struct irq_work rcu_iw;        /* Check for non-irq activity. */
    bool rcu_iw_pending;        /* Is ->rcu_iw pending? */
    unsigned long rcu_iw_gp_seq;    /* ->gp_seq associated with ->rcu_iw. */
    unsigned long rcu_ofl_gp_seq;    /* ->gp_seq at last offline. */
    short rcu_ofl_gp_flags;        /* ->gp_flags at last offline. */
    unsigned long rcu_onl_gp_seq;    /* ->gp_seq at last online. */
    short rcu_onl_gp_flags;        /* ->gp_flags at last online. */
    unsigned long last_fqs_resched;    /* Time of last rcu_resched(). */

    int cpu;
};

字段说明：

gp_seq: 当前宽限期编号，最后2bit表示宽限期状态。
cpu_no_qs: 记录本处理器是否经历静止状态，其有两个成员，
norm 表示是否经历了正常宽限期的静止状态，true表示还没有经历，为0表示经历了。
exp 表示是否经历了加速宽限期的静止状态，但是使能 CONFIG_PREEMPT_RCU 后没有赋值位置了。
s 是其二者的集合。
core_needs_qs: 若为真表示RCU需要本处理器报告静止状态。增加这个成员是为了支持CPU的热插拔，如果某个处理器下线，那么叶子节点的静止状态位图不包含该处理器，RCU不需要该处理器报告静止状态。
beenonline: 处理器最近一次状态是online.
gpwrap: 表示宽限期编号是否回绕，若gp_seq溢出，此变量会置为true。
exp_deferred_qs: 当前cpu是否在等待一个deferred QS，为true表示正在等待延迟的加速静态，rcu_report_exp_rdp() 中将其设置为false。
mynode: 指向本处理器所属的分组。
grpmask: 表示本处理器在分组位图rcu_node中的位掩码。rcu_node->qsmask 表示node中的cpu的qs情况。
ticks_this_gp: 当前gp已经历过多少个tick中断，每个tick中断中都会对它加1。
cblist: 分段回调函数链表，存放当前cpu上 call_rcu() 注册的延后执行的回调函数。
cpu: 本处理器的cpu编号。

4. struct task_struct

struct task_struct {
    ...
#ifdef CONFIG_PREEMPT_RCU //默认使能
    int                rcu_read_lock_nesting;
    union rcu_special        rcu_read_unlock_special;
    struct list_head        rcu_node_entry;
    struct rcu_node            *rcu_blocked_node;
#endif /* #ifdef CONFIG_PREEMPT_RCU */

#ifdef CONFIG_TASKS_RCU
    unsigned long            rcu_tasks_nvcsw;
    u8                rcu_tasks_holdout;
    u8                rcu_tasks_idx;
    int                rcu_tasks_idle_cpu;
    struct list_head        rcu_tasks_holdout_list;
#endif /* #ifdef CONFIG_TASKS_RCU */

#ifdef CONFIG_TASKS_TRACE_RCU
    int                trc_reader_nesting;
    int                trc_ipi_to_cpu;
    union rcu_special        trc_reader_special;
    bool                trc_reader_checked;
    struct list_head        trc_holdout_list;
#endif /* #ifdef CONFIG_TASKS_TRACE_RCU */
    ...
}

字段解释：

rcu_read_lock_nesting: 在配置 CONFIG_PREEMPT_RCU 时获取当前进程 rcu_read_lock() 嵌套的深度，若没有配置则不关注嵌套深度，直接返回0。
rcu_node_entry: 对于可抢占rcu，在读临界区被抢占后，任务通过这个成员挂在 rcu_node::blkd_tasks 链表上。

Kconfig文件中说明：CONFIG_TASKS_RCU 依赖 CONFIG_PREEMPTION，此选项启用基于任务的 RCU 实现，该实现仅使用自愿上下文切换（不是抢占！）、空闲和用户模式执行作为静止状态。不适用于手动选择。

5. struct rcu_segcblist

struct rcu_segcblist {
    struct rcu_head *head;
    struct rcu_head **tails[RCU_CBLIST_NSEGS]; //4
    unsigned long gp_seq[RCU_CBLIST_NSEGS]; //4
#ifdef CONFIG_RCU_NOCB_CPU
    atomic_long_t len;
#else
    long len;
#endif
    u8 enabled;
    u8 offloaded;
};