Chinaunix首页 | 论坛 | 认证专区 | 博客 登录 | 注册

修炼吧

为了鄙视他们,努力吧

  • 博客访问: 192970
  • 博文数量: 177
  • 博客积分: 2867
  • 博客等级: 少校
  • 技术积分: 1311
  • 用 户 组: 普通用户
  • 注册时间: 2010-05-12 00:08
文章分类

全部博文(177)

文章存档

2017年(9)

2016年(5)

2015年(9)

2014年(13)

2013年(5)

2012年(18)

2011年(117)

2010年(1)

我的朋友
微信关注

IT168企业级官微



微信号:IT168qiye



系统架构师大会



微信号:SACC2013

订阅
热词专题

分类: LINUX

代码分布

        在分析代码之前, 先看看代码的分布情况。RCU实现的代码包含在下列一些文件中,此处用到的是linux 3.6.4的代码。

  • < include/linux/rcupdate.h >     

               RCU实现的头文件,所有使用RCU的代码都需要包含它

  • < include/rcutree.h >               

               包含rcupdate.h中没有包含的函数声明。

  • < include/rcutiny.h >                

               包含rcupdate.h中没有包含的函数声明。

  • < kernel/rcupdate.c >               

               包括一些RCU实现的基础函数的实现。

  • < kernel/rcutree.h >                 

               包含Tree RCU用到的结构信息,TREE_RCU将所有的CPU组织成一颗树,通过层次结构来判别进程是否通过了宽限期,这种方式适用于多个CPU的系统。

  • < kernel/rcutree.c >                 

              包含Tree RCU的主要实现代码。

  • < kernel/rcutree_plugin.h >     

              其实也是TREE RCU实现的一部分。主要包含了抢入式TreeRCU的代码。适用于抢入式的系统,抢入式的系统适用于需要低延迟的桌面或者嵌入式系统。

  • < kernel/rcutiny.c >                  

              Tiny RCU的主要实现代码,TINY_RCU适用于单个CPU,尤其是嵌入式操作系统。

  • < kernel/rcutiny_plugin.h >      

              主要包含了抢入式Tiny RCU的代码

  • < kernel/rcu.h >                       

              定义了debug的接口,实现了__rcu_reclaim。

  • < kernel/rcutorture.c>               

             对RCU进行稳定性测试的代码,通过配置CONFIG_RCU_TORTURE_TEST,可以在系统启动的时候运行稳定性测试。

  • < kernel/rcutree_trace.c>        

             通过配置CONFIG_RCU_TRACE,可以记录RCU的运行信息。

  • < include/trace/events/rcu.h>  

             为rcutree_trace.c定义的头文件。

        RCU处理的基本流程

          RCU实现的关键集中在宽限期的处理上,这个过程需要保证销毁对象前,当前系统中所有CPU上运行的进程都通过了静止状态(quiescent state)。

         1, 程序调用call_rcu,将要删除的对象保存起来。并标记或者开始一个宽限期(同一时间只能运行一个宽限期,所以当已经有宽限期在运行的时候,其它的宽限期必须等待)。

         2, 在读取数据开始和结尾处增加 rcu_read_lock 和 rcu_read_unlock来标记读过程。为了保证删除过程知道读过程的结束,在非抢占式RCU实现中是在rcu_read_lock开始处禁止进程抢占。这样做就可以保证再运行下一次进程切换的时候,读过程已经结束。其实系统也不会去统计各个CPU上是否存在过读线程,所以所有的CPU都会在进程切换的时候通知系统它处于进制状态。当所有的CPU都通过静止状态的时候,系统就会标记它通过了一个宽限期。

         3,由于一个宽限期结束的时候,只有最后一个通过静止状态的CPU知道当前的宽限期已经结束,它并不会去通知其它CPU;同时出于性能考虑,系统也不会在宽限期结束后,马上去执行销毁过程。所以每个CPU都有一个固定的函数去检测是否有等待执行的宽限期,如果没有特别紧急的任务时,会去执行这些过程。

          接下来,要分析Tree RCU的实现,先来看看它提供的一些接口函数。

          1, call_rcu  与 synchronize_rcu都是删除对象时调用的函数。call_rcu将数据提交后会返回,而synchronize_rcu会调用call_rcu,并一直等待对象被删除后才返回。还有call_rcu_bh与synchronize_rcu_bh等接口函数,会在后续讲述。

          2,rcu_read_lock 和 rcu_read_unlock

            


    [cpp] view plain copy
    1. static inline void __rcu_read_lock(void)  
    2. {  
    3.         preempt_disable();  
    4. }  
    5.    
    6. static inline void __rcu_read_unlock(void)  
    7. {  
    8.         preempt_enable();  
    9. }  


    [cpp] view plain copy
    1. static inline void rcu_read_lock(void)  
    2. {  
    3.         __rcu_read_lock();  
    4.         __acquire(RCU);  
    5.         rcu_lock_acquire(&rcu_lock_map);  
    6.         rcu_lockdep_assert(!rcu_is_cpu_idle(),  
    7.                            "rcu_read_lock() used illegally while idle");  
    8. }  
    9. static inline void rcu_read_unlock(void)  
    10. {  
    11.         rcu_lockdep_assert(!rcu_is_cpu_idle(),  
    12.                            "rcu_read_unlock() used illegally while idle");  
    13.         rcu_lock_release(&rcu_lock_map);  
    14.         __release(RCU);  
    15.         __rcu_read_unlock();  
    16. }  


            rcu_read_lock与rcu_read_unlock在非抢占式下的实现比较简单就是 preempt_disable与preempt_enable。这样做的目的是当调用schedule的时候,就可以肯定读的过程已经结束。其它_acquire(RCU)等函数是调试用的代码,暂不做讨论。

           3, rcu_note_context_switch 在schedule中调用,每次进程切换就代表着一个静止状态。该函数会把当前的CPU状态设置为通过状态。

           4, rcu_check_callbacks 在每次时钟周期里调用(update_process_times)。通过它会触发软件中断,软件中断对应着rcu_process_callbacks,这是一个真正繁忙的函数,他会检测当前CPU的状态,向父节点传递静止状态信息,调用注册函数等一系列工作。

           在进一步了解这些函数之前,我们先来看看你Tree RCU的结构。

    TREE RCU简介

            在统计CPU的状态的时候,需要用到一个结构来存放所有CPU的状态。在早期的实现中,所有的状态都保存在一个结构中,这样做的后果是所有的CPU在更新自己状态的时候,都需要锁定该结构对象,一定程度上影响了系统性能。为了提高性能,把一定数目的CPU组成了一个节点(默认设定64个CPU为一个节点);当节点超过64个的时候,再把这些节点按64为单位划分为归属不同的父节点;如此类推,最后的一个单独的节点作为根节点。这样在更新CPU状态的时候,只需要锁定自己所属的节点就可以了。按节点设置的数目,可见这个结构只对CPU数成百上千的系统才真正起作用(我都没见过超过32个cpu的机器,不知道是啥样的感觉)。


          

              这样所有的CPU就按层级结构组织了起来,也就是一个树结构。当一个系统的CPU数少于64个的时候,只要一个rcu_node就可以。

              每个CPU在完成宽限期检测的时候,就会去更新它所属的rcu_node的值,当一个rcu_node所包含的CPU的状态都更新过以后,该node就会去更新它所属的父节点的值。直到最后一个根节点。

    TREE RCU数据结构

           为了实现该结构,系统提供了以下结构。

  • rcu_data

             由于RCU需要统计每个CPU是否通过了宽限期,提供了rcu_data来保存信息。另外每个销毁的对象并不是直接删除,也保存在rcu_data中,等到合适的时机来执行。

    [cpp] view plain copy
    1. struct rcu_data {  
    2.          /* 1) 静止状态和宽限期处理: */  
    3.          unsigned long   completed;      /* 对比 rsp->completed */  
    4.                                          /* 目的是检测宽限期是否完成. */  
    5.          unsigned long   gpnum;          /* 当前CPU上最高的宽限期数目*/  
    6.                                          /* 在宽限期开始的时候设置. */  
    7.          unsigned long   passed_quiesce_gpnum;  
    8.                                          /* 已经通过的宽限期数目. */  
    9.          bool            passed_quiesce; /* 是否通过了静止状态,在进程切换等状态会设置. */  
    10.          bool            qs_pending;     /* 对于当前执行的宽限期,该CPU是否执行完成. */  
    11.          bool            beenonline;     /* CPU是否在线,不在线的CPU需要特殊处理,以提高性能*/  
    12.          bool            preemptible;    /* 是否抢占式RCU? */  
    13.          struct rcu_node *mynode;        /* 这个CPU对应的 rcu_node */  
    14.          unsigned long grpmask;          /* 占用1bit,对应与所属的rcu_node. */  
    15.  #ifdef CONFIG_RCU_CPU_STALL_INFO  
    16.          unsigned long   ticks_this_gp;  /* The number of scheduling-clock */  
    17.                                          /*  ticks this CPU has handled */  
    18.                                          /*  during and after the last grace */  
    19.                                          /* period it is aware of. */  
    20.  #endif /* #ifdef CONFIG_RCU_CPU_STALL_INFO */  
    21.          /* 2) 批处理*/  
    22.          /* 
    23.           * 
    24.           * 当nxtlist不为空的时候,会通过nxttail划分为以下几部分 
    25.           * 每一个部分为空的时候,它的指针会被设置成与它的下一部分相同 
    26.           * 当nxtlist为空的时候,所有的nxttail都会指向nxtlist的地址,这时候nxtlist指向NULL 
    27.           * 
    28.           * [nxtlist, *nxttail[RCU_DONE_TAIL]): 
    29.           *    批处理的开始节点# <= ->completed 
    30.           *    这些节点的宽限期已经完成,可以执行销毁操作。 
    31.           *    当调用rcu_process_callbacks()的时候,下一批完成宽限期的节点也会放到这儿. 
    32.           * [*nxttail[RCU_DONE_TAIL], *nxttail[RCU_WAIT_TAIL]): 
    33.           *    批处理的开始节点 # <= ->completed - 1: 等待当前的批处理完成 
    34.           * [*nxttail[RCU_WAIT_TAIL], *nxttail[RCU_NEXT_READY_TAIL]): 
    35.           *    已知的当下次宽限期开始,可以开始等待的节点。 
    36.           * [*nxttail[RCU_NEXT_READY_TAIL], *nxttail[RCU_NEXT_TAIL]): 
    37.           *    当前不确定下次宽限期开始后,是否可以开始等待状态的节点。 
    38.           *    *nxttail[RCU_NEXT_TAIL] 的值将永远是NULL, 
    39.           *    它表示nxtlist的结束. 
    40.           * 
    41.           */  
    42.          struct rcu_head *nxtlist;  
    43.          struct rcu_head **nxttail[RCU_NEXT_SIZE];  
    44.          long            qlen_lazy;      /* # kfree_rcu调用的次数,kfee_rcu等同于call_rcu,只是它不需要销毁的对象提供销毁函数*/  
    45.          long            qlen;           /* # 当前需要执行销毁操作的次数,每次call_rcu会加一,执行过后减一*/  
    46.          long            qlen_last_fqs_check;  
    47.                                          /* 对应与qlen,最后一次执行的次数*/  
    48.          unsigned long   n_cbs_invoked;  /* 执行销毁操作的次数. */  
    49.          unsigned long   n_cbs_orphaned; /* 统计离线后CPU上剩下的callback函数的个数 */  
    50.          unsigned long   n_cbs_adopted;  /* 从离线后的CPU上移出的callback函数的个数 */  
    51.          unsigned long   n_force_qs_snap;  
    52.                                          /* 其它CPU是否在执行fore_qs? */  
    53.          long            blimit;         /* nxtlist保存的上限 */  
    54.    
    55.          /* 3) 动态时钟,*/  
    56.          struct rcu_dynticks *dynticks;  /* 每个CPU都包含一个动态时钟. */  
    57.          int dynticks_snap;              /* 用于检测CPU是否在线. */  
    58.    
    59.          /* 4) 强制执行时候处理的CPU */  
    60.          unsigned long dynticks_fqs;     /* 由于进入dynticks idle而被处理的CPU. */  
    61.          unsigned long offline_fqs;      /* 由于不在在线被处理的CPU. */  
    62.    
    63.          /* 5) __rcu_pending() 的统计信息,这些信息都是在记录调用信息的时候使用. */  
    64.          unsigned long n_rcu_pending;    /* rcu_pending() 调用次数,自从启动. */  
    65.          unsigned long n_rp_qs_pending;  
    66.          unsigned long n_rp_report_qs;  
    67.          unsigned long n_rp_cb_ready;  
    68.          unsigned long n_rp_cpu_needs_gp;  
    69.          unsigned long n_rp_gp_completed;  
    70.          unsigned long n_rp_gp_started;  
    71.          unsigned long n_rp_need_fqs;  
    72.          unsigned long n_rp_need_nothing;  
    73.    
    74.          /* 6) _rcu_barrier() 的回调函数. */  
    75.          struct rcu_head barrier_head;  
    76.    
    77.          int cpu;  
    78.          struct rcu_state *rsp;  
    79.  };  


              1,completed ,gpnum , passed_quiesce_gpnum

               gpnum表示当前正在运行的宽限期的个数,每当一个宽限期开始的时候,会设置这个值与其父节点相同。passed_quiesce_gpnum为当前CPU通过的宽限期个数,它的值在宽限期开始的时候小于gpnum,当这个CPU经过一个静止状态的时候,会把它设置成gpnum的值,通过对比它与父节点中的gpnum是否相同,可以确定该CPU是否通过了宽限期。passed_quiesce_gpnum只是表示这个CPU通过了宽限期,而completed表示所有的CPU都通过了宽限期,设置该值的同时,可以将nxtlist中等待的回调函数移动到完成队列。

             2, nxtlist 与nxttail

               nxtlist保存的是指向rcu_head对象,rcu_head的定义如下:        

    struct callback_head {
            struct callback_head *next;
            void (*func)(struct callback_head *head);
    };
    #define rcu_head callback_head

              rcu_head的结构并不复杂,它包含一个回调函数指针。而next可以把rcu_head连成一个列表。


             

               nxtlist指向一个rcu_head 列表,而nxttail的四个元素是指向指针的指针,它们指向的是rcu_head对象的next。RCU_DONE_TAIL指向的rcu_head对象之前的对象是可以销毁的对象。RCU_WAIT_TAIL指向的正在等待宽限期的元素,RCU_NEXT_READ_TAIL指向的是等待下次宽限期的元素,RCU_NEXT_TAIL指向最后一个元素,这个元素总是指向NULL。


  • rcu_node


    [cpp] view plain copy
    1. struct rcu_node {  
    2.          raw_spinlock_t lock;    /* rcu_node的锁,用来保护以下的一些成员*/  
    3.   
    4.          unsigned long gpnum;    /* 该节点当前的宽限期的数量 */  
    5.                                  /* 该值等于或者比父节点的值小1*/  
    6.          unsigned long completed; /* 该节点完成的宽限期数量*/  
    7.                                   /* 该值等于或者比父节点的值小1*/  
    8.          unsigned long qsmask;   /* 标记这个节点对应的所有CPU或者子节点是否完成了当前的宽限期*/  
    9.                                  /* 每一个bit对应一个cpu或者一个子节点.*/  
    10.          unsigned long expmask;  /* 需要执行 ->blkd_tasks 的元素 */                              
    11.                                  /*  (应用于TREE_PREEMPT_RCU). */  
    12.          atomic_t wakemask;      /* 需要唤醒kthread的CPU. */  
    13.                                    
    14.          unsigned long qsmaskinit;  
    15.                                  /* 每个宽限期开始时,用它来初始化qsmask,不存在或者不在线的CPU需要清除. */  
    16.          unsigned long grpmask;  /* 对应于父节点中的位置. */  
    17.                                  /* 只是用一bit. */  
    18.          int     grplo;          /* 该节点代表的CPU或者子节点开始的位置. */  
    19.          int     grphi;          /* 该节点代表的CPU或者子节点结束的位置. */  
    20.          u8      grpnum;         /* 下一级的CPU或者子节点的个数. */  
    21.          u8      level;          /* 跟节点是 0. */  
    22.          struct rcu_node *parent;  
    23.          struct list_head blkd_tasks;  
    24.                                  /* 阻断读关键段的任务列表 */  
    25.                                  /*  */  
    26.                       
    27.          struct list_head *gp_tasks;  
    28.                                  /* 指向第一个阻断读关键段的任务 */  
    29.                                    
    30.                                    
    31.          struct list_head *exp_tasks;  
    32.   
    33.      /*以下为抢先式下加速RCU过程的变量*/                                 
    34.   
    35. #ifdef CONFIG_RCU_BOOST  
    36.          struct list_head *boost_tasks;  
    37.                                  /* Pointer to first task that needs to be */  
    38.                                  /*  priority boosted, or NULL if no priority */  
    39.                                  /*  boosting is needed for this rcu_node */  
    40.                                  /*  structure.  If there are no tasks */  
    41.                                  /*  queued on this rcu_node structure that */  
    42.                                  /*  are blocking the current grace period, */  
    43.                                  /*  there can be no such task. */  
    44.          unsigned long boost_time;  
    45.                                  /* When to start boosting (jiffies). */  
    46.          struct task_struct *boost_kthread_task;  
    47.                                  /* kthread that takes care of priority */  
    48.                                  /*  boosting for this rcu_node structure. */  
    49.          unsigned int boost_kthread_status;  
    50.                                  /* State of boost_kthread_task for tracing. */  
    51.          unsigned long n_tasks_boosted;  
    52.                                  /* Total number of tasks boosted. */  
    53.          unsigned long n_exp_boosts;  
    54.                                  /* Number of tasks boosted for expedited GP. */  
    55.          unsigned long n_normal_boosts;  
    56.                                  /* Number of tasks boosted for normal GP. */  
    57.          unsigned long n_balk_blkd_tasks;  
    58.                                  /* Refused to boost: no blocked tasks. */  
    59.          unsigned long n_balk_exp_gp_tasks;  
    60.                                  /* Refused to boost: nothing blocking GP. */  
    61.          unsigned long n_balk_boost_tasks;  
    62.                                  /* Refused to boost: already boosting. */  
    63.          unsigned long n_balk_notblocked;  
    64.                                  /* Refused to boost: RCU RS CS still running. */  
    65.          unsigned long n_balk_notyet;  
    66.                                  /* Refused to boost: not yet time. */  
    67.          unsigned long n_balk_nos;  
    68.                                  /* Refused to boost: not sure why, though. */  
    69.                                  /*  This can happen due to race conditions. */  
    70.  #endif /* #ifdef CONFIG_RCU_BOOST */  
    71.          struct task_struct *node_kthread_task;  
    72.                                  /* kthread that takes care of this rcu_node */  
    73.                                  /*  structure, for example, awakening the */  
    74.                                  /*  per-CPU kthreads as needed. */  
    75.          unsigned int node_kthread_status;  
    76.                                  /* State of node_kthread_task for tracing. */  
    77.  } ____cacheline_internodealigned_in_smp;  


        每个rcu_node代表着 一组CPU或者子节点。在非抢占式下,它的结构并不复杂。由于可能有多个CPU对它进行处理,所有进行相应操作的时候,需要lock保护。


  • rcu_state
    [cpp] view plain copy
    1. struct rcu_state {  
    2.         struct rcu_node node[NUM_RCU_NODES];    /* 保存了所有的节点. */  
    3.         struct rcu_node *level[RCU_NUM_LVLS];   /* 每个层级所指向的节点. */  
    4.         u32 levelcnt[MAX_RCU_LVLS + 1];         /* # 每一层的节点数. */  
    5.         u8 levelspread[RCU_NUM_LVLS];           /* 每一层的CPU/节点数. */  
    6.         struct rcu_data __percpu *rda;          /* 指向rcu_data. */  
    7.         void (*call)(struct rcu_head *head,     /* rcu_barrier指向的回调函数. */  
    8.                      void (*func)(struct rcu_head *head));  
    9.   
    10.         /* The following fields are guarded by the root rcu_node's lock. */  
    11.   
    12.         u8      fqs_state ____cacheline_internodealigned_in_smp;  
    13.                                                 /* 调用force_quiescent_state时的状态. */  
    14.         u8      fqs_active;                     /* force_quiescent_state() 正在运行*/  
    15.                                                   
    16.         u8      fqs_need_gp;                    /* 因为 force_quiescent_state() 正在运行*/  
    17.                                                 /* 一个CPU需要运行的宽限期被阻止*/  
    18.   
    19.         u8      boost;                          /* 加速. */  
    20.         unsigned long gpnum;                    /* 当前的宽限起数量. */  
    21.         unsigned long completed;                /* # 最后一次完成的宽限期数量. */  
    22.   
    23.         /* 以下的成员被根rcu_node的lock保护. */  
    24.   
    25.         raw_spinlock_t onofflock;               /* 开始一个新的宽限期的时候,阻止CPU上下线*/  
    26.                                                   
    27.         struct rcu_head *orphan_nxtlist;        /* 等待宽限期的孤儿回调函数的列表 */  
    28.                                                   
    29.         struct rcu_head **orphan_nxttail;       /* 以上列表的结尾. */  
    30.         struct rcu_head *orphan_donelist;       /* 需要执行的孤儿回调函数列表 */  
    31.                                                   
    32.         struct rcu_head **orphan_donetail;      /* 以上列表的结尾. */  
    33.         long qlen_lazy;                         /* 懒惰回调函数的个数. */  
    34.         long qlen;                              /* 总的回调函数的个数. */  
    35.         struct task_struct *rcu_barrier_in_progress;  
    36.                                                 /* 调用rcu_barrier()的进程, */  
    37.                                                 /* 没有的话指向NULL. */  
    38.         struct mutex barrier_mutex;             /* 执行barrier需要的互斥锁. */  
    39.         atomic_t barrier_cpu_count;             /* # 等待barrier的CPU数 . */  
    40.         struct completion barrier_completion;   /* 在barrier结束的时候调用. */  
    41.         unsigned long n_barrier_done;           /* 在_rcu_barrier()开始结束处都需要调用++ */  
    42.                                                   
    43.         raw_spinlock_t fqslock;                 /* 只有一个进程能调用 force_quiescent_state().*/  
    44.                                                   
    45.         unsigned long jiffies_force_qs;         /* force_quiescent_state()开始的时间 */  
    46.                                                   
    47.         unsigned long n_force_qs;               /* 调用force_quiescent_state()的次数 */  
    48.                                                   
    49.         unsigned long n_force_qs_lh;            /* 因为lock不可用,而退出force_quiescent_state()的次数 */  
    50.                                                   
    51.         unsigned long n_force_qs_ngp;           /* 因为当前有宽限期执行,而退出force_quiescent_state()的次数*/  
    52.                                                   
    53.         unsigned long gp_start;                 /* 宽限期开始的时间*/  
    54.                                                   
    55.         unsigned long jiffies_stall;              
    56.                                                
    57.         unsigned long gp_max;                   /*  最长的宽限的jiffie数 */  
    58.                                                   
    59.         char *name;                             /* 结构的名字. */  
    60.         struct list_head flavors;               /* 系统中的rcu_state. */  
    61. };  

            rcu_state 保存了所有的node,宽限期的判断只要取出根节点,也就是第一个元素就可以。还有一些初始化要用到的变量。还有孤儿回调函数用于处理离线CPU遗留的信息。剩下还有很多统计信息,这些内容在讲解代码实现的时候再仔细考虑。

  • 阅读(4859) | 评论(0) | 转发(0) |
    0

    上一篇:TREE RCU 实现之一:数据结构

    下一篇:没有了

    给主人留下些什么吧!~~
    评论热议
    请登录后评论。

    登录 注册