cfq io调度算法简介

本文以rhel5.6所使用的2.6.18内核进行分析。

1 cfq用到的几个数据结构
~~~~~~~~~~~~~~~~~~~~~~~~
  在cfq中，进程被按照优先级分组。cfq尽量优先处理高优先级组中的请求，同
  时也避免低优先级组中的请求被饿死。一个进程可能同时向多个不同的块设备
  提交io请求，而一个使用cfq调度算法的块设备又要处理多个进程中传下来的
  请求，并将它们分组。所以，cfq使用下面这些数据结构分别描述进程，优先
  级组，以及一个cfq块设备。

1.1 struct io_context
======================
   每个进程都有一个io_context结构体，从其定义中包含
   struct as_io_context *aic;
   和
   struct rb_root cic_root;
   这两位来看，它是专为as和cfq两个io调度算法准备的，在cfq中，它是
   struct cfq_io_context的基类。

1.2 struct cfq_io_context
==========================
   cfq_io_context是cfq中为每个进程分配的结构体，继承自io_context。每个
   进程都只有一个io_context，但它同时向多少个使用cfq调度算法的块设备提
   交io请求，就会有多少个cfq_io_context，这些个cfq_io_context被组织在
   一个红黑树中，树根是io_context中的cic_root，cfq_io_context中的"void
   *key"位用作红黑树的键值。由于每个cfq_io_context对应一个使用cfq调度
   算法的块设备，所以实际上cfq使用struct cfq_data结构体的地址作为键值，
   每个使用cfq算法的块设备都有唯一的一个struct cfq_data结构体。

1.3 struct cfq_queue
=====================
   当多个进程向同一个块设备提交io请求的时候，cfq会对进程按照优先级进行
   分组，进程的优先级信息存储在进程结构体的"unsigned short ioprio"位中，
   如果该位没有进行设置，cfq按照进程的nice值计算出一个优先级。默认共有
   8个优先级，对于每个优先级组，使用一个cfq_queue结构体进行表示。

1.4 struct cfq_data
====================
   每个使用cfq调度算法的块设备都有一个cfq_data结构，保存在struct
   elevator_queue的void *elevator_data位中。

1.5 struct cfq_rq
==================
   每个request都有一个cfq_rq，保存在request的void *elevator_private位
   中。

2 cfq_set_request函数
~~~~~~~~~~~~~~~~~~~~~~
  每当有一个新的io请求提交之后，电梯算法都会调用cfq_set_request函数让
  cfq为该请求分配必要的资源。
  首先调用cfq_get_io_context函数获取一个struct cfq_io_context结构，如
  果没有的话cfq_get_io_context函数会分配一个新的。
  接下来看cfq_io_context的"struct cfq_queue *cfqq"位有没有包含一个
  struct cfq_queue，如果没有的话就调用cfq_get_queue函数。
  cfq_get_queue函数计算当前进程的io优先级，并检察当前块设备的struct
  cfq_data结构中有没有对应该优先级的cfq_queue，有的话就返回，没有的话
  就分配一个新的。然后调用cic_set_cfqq函数让当前进程的cfq_io_context指
  向该cfq_queue。
  接下来分配一个新的对应于当前请求的struct cfq_rq结构。

3 cfq_insert_request函数
~~~~~~~~~~~~~~~~~~~~~~~~~
  调用完cfq_set_request函数后，电梯算法会调用cfq_insert_request将新提
  交的请求插入到cfq的数据结构中。
  首先检查cfq_queue的优先级是否改变，如果改变将相应的信息更新。然后将
  该请求对应的cfq_rq插入到以cfq_queue的"struct rb_root sort_list"为根
  的红黑树中。将请求按照提交时间的先后顺序放到cfq_queue的fifo链表上，
  如果该请求是可合并的，则将请求放到cfq_data的哈希表中，在合并请求时，
  会用到该哈希表。最后，调用cfq_crq_enqueued函数更新一些时间戳以及统计
  信息。

4 cfq_dispatch_requests函数
~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  每当电梯算法要补充一些请求到请求队列上的时候，会调用
  cfq_dispatch_request函数。
  首先调用cfq_select_queue选择一个优先级队列，然后调
  用__cfq_dispatch_requests函数将该优先级队列上的一部分请求放到请求队
  列上。
  选择优先级队列时，总是从最高等级的优先级队列开始选择，但每个等级都有
  一个时间片，如果该等级的时间片到期，则选择下一个等级的队列。

5 merge
~~~~~~~~

5.1 cfq_merge函数
==================
   电梯算法调用cfq_merge函数判断一个新的请求是否能和以前的请求合并。
   首先判断是否能进行后向合并。cfq_data中有一个哈希表，储存了所有可以
   合并的请求，并且以请求的结束扇区号作为键值。所以，以当前请求的起始
   扇区号作为键值进行搜索，如果能够搜到一个请求，则说明搜到的请求的结
   束扇区号和当前请求的起始扇区号相等，可以进行后向合并。
   如果没有找到能够进行后向合并的请求，则尝试寻找是否有能进行前向合并
   的请求。以当前请求的结束扇区号为键值，在与当前请求的io优先级相等的
   cfq_queue的红黑树中寻找。由于该红黑树中的成员是以请求的起始扇区号为
   键值的，如果找到，说明可以进行前向合并。
   cfq_merge的返回值会告诉调用它的函数是可以进行前向合并，还是后向合并，
   还算不可以合并。如果可以合并，会将可用来合并的请求放到struct
   request **req中返回。

5.2 cfq_merged_request函数
===========================
   所谓合并，就是将一个新传递进来的bio放到一个以前的request中。实际的
   合并操作是在ll_rw_blc.c和elevator.c中完成的。在合并完成之后，电梯算
   法会调用cfq_merged_request函数让cfq进行一些必要的更新。由于进行了合
   并，request的起始扇区号和结束扇区号可能会发生变化，而cfq内部所用的
   哈希表以及红黑树是以这两个值作为键值的。所以,cfq_merged_request的作
   用就是检验这两个值是否变化，若变化了则以新的键值放置相应的数据结构
   成员

linux的deadline io 调度算法分析

1 linux的deadline io 调度算法分析
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  以rhel5.6系统（kernel version 2.6.18）为基础分析linux内核的块设备层
  的deadline io 调度算法。

2 把bio添加到请求中以及把请求添加到请求队列中
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

2.1 最简单的情况，请求队列中一个请求都没有的时候，添加第一个bio
================================================================
   bio通过generic_make_request函数传递进来。generic_make_request函数会
   调用请求队列的make_request_fn函数指针完成实际的io操作。如果使用电梯
   算法，请求队列的make_request_fn函数指针将指向__make_request函数。
   我们只考虑与电梯算法相关的部分。

   首先，调用elv_merge函数检查是否可以将当前的bio合并到以前的request
   中。如果是第一次执行到这里，当然没有可以合并的request，于是调用
   get_request_wait函数获取一个新的request，然后调用
   init_request_from_bio函数将bio添加到request中。接下来调用
   add_request函数将request添加到request_queue中。

   add_request中的函数调用流程：
   add_request->__elv_add_request->elv_insert
   elv_insert函数会将新创建的request挂到request_queue的queue_head链表
   上，并让request_queue的last_merge指针指向当前的request。最
   后，elv_insert函数会调用到函数指针：
   q->elevator->ops->elevator_add_req_fn
   如果deadline是该块设备的io调度算法的话，这个指针就指向了
   deadline_add_request函数。

   deadline算法中有两个红黑树（读写请求各有一个），两个双向链表（读写
   请求各有一个），一个哈希表（所有读写请求都在同一个哈希表上）。

   deadline_add_request函数会将传递进来的request添加到与请求的读写方
   向相对应的红黑树与双向链表中，以及哈希表上。同时，也记录下这个请求
   的到期时间。

   deadline中的红黑树以起始扇区号作为键值进行排序。双向链表按照request提
   交进来的先后顺序进行排序，最先加进来的request放在链表的头部。因此，每
   新添加一个请求的时候，都放在链表的尾部。哈希表使用request的结束扇
   区号（即rq->sector + rq->nr_sectors）作为键值进行索引。读请求的期
   满值默认为0.5秒，写请求的期满值默认为5秒。在合并与分发请求时，我们
   会看到deadline算法如何使用这些数据。

   调用完add_request函数后，__make_request的任务基本就结束了。每一个
   请求队列，在真正处理请求的时候都会有一个延迟，一般默认设为3毫秒。
   如果这3毫秒内又有request到来，则将该请求提交给io调度算法，并重新设
   置延迟的期满时间为3毫秒。

2.2 将bio merge到request中
===========================
   每当一个bio提交到__make_request函数中的时候，该函数总是调用
   elv_merge函数检查是否能将当前的bio合并到以前的request中。elv_merge
   函数分两步进行判断。

   第一步，判断判断bio是否可以合并到request_queue的last_merge指针指向
   的request。last_merge总是指向上一次提交进来的请求。如果进行连续读
   写的话，这是可能性最大的情况。判断的方法很简单，首先看request的结
   尾扇区号是否等于bio的起始扇区号，如果是的话就能够进行back merge，
   然后判断request的起始扇区号是否等于bio的结尾扇区号，如果是的话就能
   够进行front merge。

   第二步，如果bio不能和last_merge指向的request进行合并的话，则调用io
   调度算法的elevator_merge_fn成员函数，判断bio是否能和某个request进
   行合并。

   对于deadline调度算法，elevator_merge_fn指向deadline_merge函数。该
   函数首先判断是否能进行back merge。以bio的起始扇区号为键值在哈希表
   中寻找。由于deadline中的哈希表是以request的结束扇区号为键值的，所
   以如果找到这样的request的话，说明这个request的结语扇区号与bio的起
   始扇区号相等，因此bio可以back merge到这个request中。如果没有找到这
   样的request，说明无法进行back merge，则继续尝试能否进行front merge。
   方法是以bio的结束扇区号为键值在红黑树中进行搜索。红黑树是以request
   的起始扇区号为键值进行排序的，因此，如果找到符合条件的request，说
   明该request的起始扇区号等于bio的结束扇区号，可以进行front merge。
   无论是back merge还是front merge，如果找到符合条件的request的话，都
   要把request从哈希表上拿下来，再按照新的键值重新放上去，至于红黑树，会
   在后续的操作中进行处理。

   若是可以进行合并，elv_merge会返回用来合并的request指针，并且，通过
   返回值表示是何种合并，ELEVATOR_BACK_MERGE表示back merge，
   ELEVATOR_FRONT_MERGE表示front merge，ELEVATOR_NO_MERGE表示无法进行
   合并。

2.2.1 back merge
-----------------
    若是进行back merge，则调用函数指针q->back_merge_fn对request_queue
    和request进行一些必要的处理，这个指针通常指向ll_back_merge_fn函数。
    然后修改request的biotail，biotail->next，以及nr_sector等位，将bio
    添加到request中。接下来调用attempt_back_merge函数，该函数的作用是
    检查是否可以进一步的进行合并，例如，原先请求队列中有这样两个请
    求，request1写块设备的secotr0到sector4，request2写块设备的
    sector 8到sector 12。现在新加入的bio写sector5到sector7，bio被合并
    到了request1中，request1变成写sector0到sector7，此时，request1和
    request2可以进行合并了。若发生这种情况，attempt_back_merge函数会
    进行处理，若没有，则调用elv_merged_request函数进行最后的收尾处理。
    该函数会调用调度器的elevator_merged_fn方法，对于deadline调度器，
    该方法指向deadline_merged_request函数。该函数的作用很简单，由于进
    行了合并，request的起始扇区号和结束扇区号可能改变了，用新的扇区号
    做键值更新request在哈希表和红黑树中的位置。

2.2.2 front merge
------------------
    与back merge的处理基本对称，不再赘述。

3 从请求队列中取出一个请求
~~~~~~~~~~~~~~~~~~~~~~~~~~~
  正常情况下，每当request_queue等待3毫秒还没有新的bio提交后，就会出发
  unplug，最终会调到request_queue的request_fn方法。以scsi磁盘驱动为
  例，该方法指向scsi_request_fn函数。scsi_request_fn会调用
  elv_next_request函数来从请求队列中取出一个请求进行处理。而该函数会
  调用__elv_next_request找出一个合适的请求。

  __elv_next_request函数首先从request_queue的queue_head链表上寻找
  request，如果找到的话就返回这个request，没找到的话就调用调度器的
  elevator_dispatch_fn方法，通常，这个方法会将一些request放到
  queue_head链表上。然后再检查request_queue的queue_head链表。一直循
  环，直到从queue_head上找到一个request，将其返回，或者
  elevator_dispatch_fn方法返回0，则__elv_next_request函数返回一个空指
  针。

  对于deadline调度器来说，elevator_dispatch_fn函数指针指向
  deadline_dispatch_requests函数。

  deadline_dispatch_requests函数负责从已经提交给调度器的request中选择
  一个放到request_queue的queue_head链表中。

  为了优化读写磁盘的效率，deadline调度器会对请求进行批处理，每当选定
  一个请求方向时（读或写），总是连续处理该方向上的16个请求。然后才重
  新选择另一个方向上的请求。当然，如果某个方向上已经没有请求了，则马
  上选择另一个方向上的请求。

  每当处理了一个方向上的请求，就将该方向上的下一个请求放到
  next_drq[WRITE]中或next_drq[READ]中。因此，当进入
  deadline_dispatch_requests函数的时候，首先判断next_drq[WRITE]或
  next_drq[READ]是否为空，这两个指针至多有一个不为空。如果其中有一个
  不为空，我们就获得了一个request。接下来判断这个request和上一次发送
  的请求是否是连续的，若不是连续的，则打破批处理，然后判断当前的批处
  理进行了多少次，如果超过了最大的允许次数，也要打破批处理，重新选择
  request。这是为了防止在某一个方向上有大量连续的request，导致饿死了
  另一个方向上的request。

  如果确定要继续批处理，则直接跳到函数的末尾，即标签
  “dispatch_find_request”处，递增批处理的统计次数，将同方向上的下一个
  请求放到next_drq[WRITE]或next_drq[READ]中，记录当前request的结束扇区
  号，以便再进入本函数时判断下一个request是否和当前这个是连续的。最后
  把这个请求从deadline算法内部维护的哈希表，红黑数和链表上面移除，放到
  request_queue的queue_head链表上。

  如果前面判断不进行批处理，则先看是否有读请求需要处理。若读写请求都
  有的话，就把starved变量加一，表示忽略了一次写请求。如果忽略的写请求
  次数超过了变量writes_starved的值（默认为2），那么就不再忽略写请求，
  跳转到标签“dispatch_writes”的位置，将变量data_dir设为WRITE，表示提
  交一个写请求。否则将data_dir设为READ，表示提交一个读请求。

  现在已经选择了request的方向（READ或WRITE），接下来判断在该方向上最
  先进来的request是否已经超时了，或者该方向上还有没有request的起始扇
  区号比上一个请求更靠后的request了（这样的request即使不连续也可以让
  磁盘的磁头大体上朝一个方向移动）。如果两个条件中有一个条件为真，就
  选择该方向上时间最早的request提交。如果这两个条件都为假的话，即没有
  任何请求超时，而且有一个起始扇区号比上一个request大的请求，就提交这
  个请求。

  完。

linux内核中SH_DIV宏分析

在读linux内核中关于时钟部分的代码时，遇到了一个叫SH_DIV的宏，它包含的
技巧颇为有趣。自己写代码时可能用得到。

下面是这个宏的注释和定义：

/* Suppose we want to devide two numbers NOM and DEN: NOM/DEN, the we can
 * improve accuracy by shifting LSH bits, hence calculating:
 *     (NOM << LSH) / DEN
 * This however means trouble for large NOM, because (NOM << LSH) may no
 * longer fit in 32 bits. The following way of calculating this gives us
 * some slack, under the following conditions:
 *   - (NOM / DEN) fits in (32 - LSH) bits.
 *   - (NOM % DEN) fits in (32 - LSH) bits.
 */
#define SH_DIV(NOM,DEN,LSH) (   (((NOM) / (DEN)) << (LSH))              \
                             + ((((NOM) % (DEN)) << (LSH)) + (DEN) / 2) / (DEN))


计算 (N << L) / D，可以等价于下面的算式：
(N / D) << L + ( (N % D) << L + (D / 2) ) / D

下面是推导过程：

N = (N / D) * D + (N % D)

N << L = N * 2^L
       = ( (N / D) * D + (N % D) ) * 2^L
       = (N / D) * D * 2^L + (N % D) * 2^L

(N << L) / D = ( (N / D) * D * 2^L + (N % D) * 2^L ) / D
             = ( (N / D) * D * 2^L ) / D + ( (N % D) * 2^L ) / D
         = (N / D) * 2^L + ( (N % D) * 2^L ) / D
         = (N / D) << L + ( (N % D) << L ) / D

这时与最终的等式只差一个(D / 2)，当在C语言中进行除法运算(N / D)时，结
果总是向下取整，余数部分全都被舍去了，因此，在计算除法前给被除数加上除
数的一半，可以起到四舍五入的效果，即：(N + (D / 2)) / D。
所以，在前面推导过程的最后一步时，在除以D前要加上(D / 2)，即：
(N << L) / D = (N / D) << L + ( (N % D) << L + (D / 2) ) / D

甄姬洛神后摸桃子的概率

我考虑的是这样一种情况： 不包括任何扩展牌，牌堆中共104张牌，52红，52黑，红牌中有8张桃子。牌洗好 后甄姬开始洛神，直到洛神失败，然后抓两张牌。计算这种情况下甄姬至少摸到 一张桃子的概率。 首先，看白板武将至少摸到一张桃子的概率如何计算 ： 先 计算白板武将一张桃子都摸不到的概率，然后用1减去它得到的就是至少摸到 一张桃子的概率。白板武将摸两张牌，相当于从104张牌中随机抽出两张牌，共有 104*103种抽法。不是桃子的牌共有96张，抽出两张不是桃子的牌，共有96*95种 抽法。所以，白板武将摸不到桃子的概率p1 = (96*95)/(104*103)。1-p1得到的 就是白板武将至少摸到一张桃子的概率。 为了给计算甄姬摸桃子的概率做铺垫，再考虑另一种计算白板武将摸桃子的概率。 还是先考虑一张桃子的摸不到的概率。 104 张牌进行排列组合，共有104的阶乘，即104!种排列方法。再看看前两张牌都 不是桃子共有多少种排列方法：先从96张不是桃子的牌中取一张放在最上面， 再 从剩下的95张不是桃子的牌中取1张放在牌库顶的第二张，再将剩下的102张牌任 意排列，共有：96*95*102!种排列方法。因此，白板武将摸不到 桃子的概率p1 = (96*95*102!)/(104!) = (96*95)/(104*103)与前一种方法的计算结果一致。 现在，我们来看甄姬洛神直到失败后，至少摸到一张桃子的概率。依然，我们还 是计算甄姬一张桃子都摸不到的概率，然后用1减去它得到甄姬至少摸到一张桃子 的概率。 104张牌进行排列组合，共有104!种排列方法。 甄姬洛神后抓牌，共有如下这么多种可能： 0 洛神到0张黑牌，即一张牌都没洛到。0.1 洛神的判定牌不是桃子从 44张不是 桃子的牌中任选一张放在牌库顶，不是桃子的牌共96张，其中有一张红的作为判 定牌放在牌库顶了，从剩下的95张中选一张放在牌库顶的第二张的位 置，再从剩 下的94张中选一张放在第三张的位置（我们现在计算的是1张桃子都摸不到的概率， 所以从不是桃子的牌中选2张给甄姬摸），1张放在了牌库顶，不 是桃子的牌中选 出了两张给甄姬摸，总共104张牌，还剩101张牌可以任意排列，共有101!种排列 方法。因此，洛神第一张就是红色，并且不是桃子共有这末多种情况：44 * 95 * 94 * 101!  0.2 洛神的判定牌是桃子与0.1的算法类似，从8张桃子中选一 张放在牌库顶，然后从96张不是桃子的牌中选1张放在牌库顶第二张，再从剩下的 95张不是桃子的牌中选一张放在牌库顶第三张，剩下的101张牌任意排列，共有这 末多种情况：8 * 96 * 95 * 101! 1 洛神到1张黑牌。从52张黑牌中选1张放到牌库顶，共有52种情况，接下来： 1.1 判定牌不是桃子从44张不是桃子的红牌中选1张放到洛神的牌后面，洛神1张 牌加上判定牌1张，还剩94张不是桃子的牌，从中选一张放在判定牌后面，再从剩 下的93张不是桃子的牌中选一张放在后面，此时包括桃子总共还剩100张牌，可以 任意排列，于是共有这末多种情况：52 * 44 * 94 * 93 * 100!  1.2 判定牌是 桃子从8张桃子中选1张放到洛神的牌后面，除去洛神的1张牌，还有95张牌不是桃 子，从中选1张放到判定牌后面，再从剩下的94张不是桃子的牌中选1张放到后面， 然后剩下的100张牌任意排列，共有这末多种情况：52 * 8 * 95 * 94 * 100! 2 洛神到2张黑牌从52张黑牌中选1张放到牌库顶，再从剩下的51张黑牌中选1张放 到牌库顶第二张，共有52*51种情况2.1 判定牌不是桃子从44张不是桃子的红牌中 选1张放到洛神的牌后面，洛神2张加上判定牌1张，还剩93张不是桃子的牌，从中 选1张放到判定牌后面，再从剩下的92张不是桃子的牌中选1张放到后面，一共还 剩99张牌，可以任意排列，共有这末多种情况：(52 * 51) * 44 * 93 * 92 * 99!  2.2 判定牌是桃子从8张桃子中选1张放到洛神的牌后面，除去洛神2张牌， 还剩94张不是桃子的牌，从中选1张放到判定牌后面，再从剩下的93张不是桃子的 牌中选1张放到后面，一共还剩99张牌，可以任意排列，共有这末多种情况： (52 * 51) * 8 * 94 * 93 * 99! 依此类推，可以得到： 3 洛神到3张黑牌从52张牌中选3张放到牌库顶，共有52 * 51 * 50种情况3.1 判 定牌不是桃子(52 * 51 * 50) * 44 * 92 * 91 * 98!  3.2 判定牌是桃子 (52 * 51 * 50) * 8 * 93 * 92 * 98! ...... 51 洛神到51张黑牌从52张牌中选51张放到牌库顶，共有52 * 51 * 50 * ...... * 2种情况51.1 判定牌不是桃子(52 * 51 * ... * 2) * 44 * 44 * 43 * 50!  51.2 判定牌是桃子(52 * 51 * ... * 2) * 8 * 45 * 44 * 50! 52 洛神到52张黑牌52.1 判定牌是桃子(52 * 51 * ... * 2 * 1) * 44 * 43 * 42 * 49!  52.2 判定牌不是桃子(52 * 51 * ... * 2 * 1) * 8 * 44 * 43 * 49! 将上面的所有情况相加，得到的就是所有洛神后摸不到桃子的情况。经计算得到， 洛神后摸不到桃子共有这末多种情况： no_peach = 8768393644112035467653013895319007081912845854144094315049335792122609241987921866302232452367163796631068635340901979516433835590933660303360000000000000000000000000 又由于104张牌全排列共有104!种情况 因此，甄姬摸不到桃子的概率p2 = no_peach / 104! no_peach刚好可以被102!整除，因此计算p2时分子分母同时约去102! 得到：p2 = 9120 / (104 * 103) = (96 * 95) / (104 * 103) = p1 即，甄姬洛神后摸不到桃子的概率，和白板武将摸两张牌后摸不到桃子的概率是 一样的，所以，他们至少摸到1张桃子的概率也是一样的，均为1 - (96 * 95) / (104 * 103)，约等于0.148618371919。 我把计算no_peach的值的程序放到github上了 https://github.com/yupeng820921/luoshen calc.py 是个python写的小程序。

linux内核raid5一次整条带写操作的流程（基于2.6.33内核）

Table of Contents
=================
1 raid5写入数据的顺序
2 make_request函数
        2.1 rand5_compute_sector
        2.2 get_active_stripe
            2.2.1 get_free_stripe
            2.2.2 init_stripe
                2.2.2.1 raid5_build_block
            2.2.3 get_active_stripe的其他部分
            2.2.4 __find_stripe
        2.3 add_stripe_bio
        2.4 在add_stripe_bio和release_stripe之间的操作
        2.5 release_stripe
            2.5.1 __release_stripe
3 raid5d
    3.1 __get_priority_stripe
    3.2 handle_stripe
        3.2.1 handle_stripe5
            3.2.1.1 handle_stripe_dirtying5
                3.2.1.1.1 schedule_reconstruction
            3.2.1.2 raid_run_ops
            3.2.1.3 handle_stripe5结束
    3.3 release_stripe
4 ops_complete_reconstruct
5 再次进入raid5d
    5.1 ops_run_io
6 raid5_end_write_request
7 第三次进入raid5d
    7.1 handle_stripe_clean_event
    7.2 release_stripe


1 raid5写入数据的顺序
######################
  假设，stripe size是4k大小，chunk size是32k，共有4块盘。首先，第一块
  盘的4k数据会写入第一块盘的第一个chunk的第一个stripe，如图1所示：

图1

图中桔黄色的方块表示写入的数据，蓝色的方块表示该处将用于存储校验数
  据。图中只画出了第一个chunk，所以校验数据都存于最后一个磁盘中。
  接下来的4k数据会写入第一块盘的第一个chunk的第二个stripe，如图2所示：

图2

直到写入8次4k的数据后，第一块盘的第一个chunk全部写完，如图3所示：

图3

写完这32k数据后，接下来的4k数据会写入第二块盘的第一个chunk的第一个
  stripe，如图4所示：

图4

依此类推，直到第三块盘的第一个4k数据写完，此时，第一个stripe即
  stripe0就被填满了，如图5所示：

图5

在raid5的make_request函数中，如果能够找到一个stripe来描述当前这次写
  操作，则将该stripe提交到一个全局链表中，然后唤醒守护进程raid5d来进
  行处理，make_request并不等到raid5d将数据真正写入磁盘，就直接返回了。
  所以，有大量的数据连续写入时，make_request函数会被连续调用，每次使
  用一个stripe来描述这次任务，就返回了。默认一共有256个stripe可用。当
  这256个stripe都使用完了之后，再有写操作的时候，make_request函数就会
  进入休眠，直到至少有四分之一的stripe被释放之后才会被唤醒，使用新释
  放出来的stripe来描述新的写操作。
  我们来看一下第一个stripe(即stripe0)中的数据的处理流程。

2 make_request函数
###################
  对一次正常的写操作，make_request函数中需要调用4个比较重要的函数。下
  面依次介绍。

2.1 rand5_compute_sector
~~~~~~~~~~~~~~~~~~~~~~~~~
    首先会调用raid5_compute_sector函数通过整个md设备的扇区号
    logical_sector换算出在实际磁盘上对应的扇区号new_sector，以及需要使
    用的是第几块磁盘dd_idx。我们只看和stripe0相关的部分。
    在本例中，第一次写入磁盘的4k数据会落入到stripe0中，即
    logical_sector=0，此时计算出的new_sector=0，dd_idx=0，即写入第一块
    磁盘的第一个sector。
    然后，在写入第九个4k的数据的时候，又落入到stripe0中，此
    时，new_sector = 0, dd_idx = 1, logical_sector = 64。
    在写入第17个4k的数据时，会再次落入到stripe0中，此时，new_sector =
    0, dd_idx = 2, logical_sector = 128。
    至此，第一个stripe被填满。
    每次调用raid5_compute_sector函数后，会返回new_sector和dd_idx两个变
    量。同一个stripe中的每块盘的扇区号是一样的，所以通过new_sector的值
    来判断本次写操作发生在哪个stripe中，并使用一个stripe_head类型的结
    构体来描述这次写操作。

2.2 get_active_stripe
~~~~~~~~~~~~~~~~~~~~~~
    分配stripe_head的操作是在get_active_stripe函数中完成的。首先，这个
    函数会尝试调用__find_stripe函数查看本次操作所在的stripe是不是已经
    在使用中了，如果是的话，就不用新分配stripe了。
    在第一次写入4k数据时，stripe0肯定不在使用中，所以__find_stripe函数
    的返回值是NULL，然后，会调用get_free_stripe函数去获得一个空闲的
    stripe。

2.2.1 get_free_stripe
======================
     进入get_free_stripe函数看一下，该函数很简单，从inactive_list链表
     中取下一个sh，然后给active_stripes的值加一，表示又有一个stripe被
     使用了。此外，还会将sh从它所在的hash表中拿下来（如果它确实挂在一
     个hash表上的话）。这个hash表是在__find_stripe中使用的，介绍后续的
     写操作时会进行说明。

2.2.2 init_stripe
==================
     如果成功的分配到了一个sh，就会调用init_stripe函数对该sh进行初始化。
     包括这个stripe的起始扇区号，使用第几块盘存放校验数据，以及将它的
     状态sh->state设成0。后面我们会看到这个状态在不停的变化。
     对于属于这个sripe的每一个块设备，都有一个r5dev类型的结构体来描述。
     这些个r5dev型的结构体也需要初始化。首先将表示该块设备状态的标志
     dev->flags清零。然后调用raid5_build_block函数初始化与bio相关的变
     量。

2.2.2.1 raid5_build_block
--------------------------
      raid5_build_block函数首先设置提交一次bio所使用的bi_io_vec以及存
      放数据的page之类的变量。然后会调用这样一个函数：
      dev->sector = compute_blocknr(sh, i, previous);
      这里计算出的sector是该磁盘在该stripe中的起始扇区，在整个md设备中
      的扇区号。

2.2.3 get_active_stripe的其他部分
==================================
     在get_active_stripe函数的末尾部分，有这样一句话：
     atomic_inc(&sh->count);
     将sh的记数器加1，后面会介绍到，每当进入release_stripe函数时，会将
     count的值减1，如果减到0了就表示当前对这个sh的处理都完成了，唤醒守
     护进程，来决定对sh的下一步处理。

2.2.4 __find_stripe
====================
     对于写入raid设备的第一个4k的数据，__find_stripe函数会返回空。但当
     写入第九个4k的数据时，也就是像图2中所示的情况发生时，__find_stripe函
     数通过sector为key值在一个全局hash表中查找，由于这时的sector值和第
     一个4k数据的sector值是一样的，而写入第一个4k数据时，在init_stripe
     函数中已经把那时分配到的sh以sector为key值挂到hash表中了，所以这
     时__find_stripe函数会找到写入第一个4k数据所用的sh，也就是用来描述
     stripe0的sh。

2.3 add_stripe_bio
~~~~~~~~~~~~~~~~~~~
    add_stripe_bio函数写在一个条件表达式中的不起眼的位置上，但功能很重
    要。
    首先判断是要执行读操作还是写操作。
    然后用一个临时变量bip指向写磁盘时需要使用的bio（即towrite）的地址，
    后面操作bip就等于改变了towrite的值。然后判断是否发生了overlap的情
    况，也就是前面已经有一个读写请求发生在这个stripe的这块盘上，而本次
    操作又发生在同一个stripe的同一块盘上，并且两次读写数据的位置还有重
    叠。对于我们的顺序写操作，肯定是不会发生这种情况的。
    接下来，对于写操作，要判断是否发生了overwrite的情况。所谓
    overwrite，就是这次写操作是不是覆盖了stripe在这块磁盘上的整个区间。
    如果是的话，在计算xor校验值的时候，对于这块磁盘，就直接使用上层传
    下来的数据，如果不是的话，就需要读回stripe在这块磁盘上的数据到内
    存，然后在把上层传下来的数据覆盖到内存，再计算xor，最后把内存中的
    数据写入磁盘。
    判断写入数据是否覆盖整个stripe的方法也很简单，如果写入数据的起始扇
    区号小于等于stripe的扇区号(bi->bi_sector <= sector)，并且写入数据的
    结束扇区号大于等于stripe的结束扇区号(sector >=
    sh->dev[dd_idx].sector + STRIPE_SECTORS)，那么这次写操作就是
    overwrite的。
    在我们的例子中，每次写入4k数据，刚好等于stripe的大小，所以是
    overwrite的。因此，下面语句会被调用：
    set_bit(R5_OVERWRITE, &sh->dev[dd_idx].flags);

2.4 在add_stripe_bio和release_stripe之间的操作
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    此时make_request函数中会执行两步比较有意义的操作：
    set_bit(STRIPE_HANDLE, &sh->state);
    clear_bit(STRIPE_DELAYED, &sh->state);
    设置STRIPE_HANDLE位很重要，它表示这个stripe需要进一步的处理，在
    release_stripe函数中会通过该位来判断是否需要唤醒守护进程。

2.5 release_stripe
~~~~~~~~~~~~~~~~~~~
    接下来进入make_request中会调用到的最后一个比较重要的函数。
    release_stripe函数只有几行：获取锁，调用__release_stripe函数，释放
    锁。所以真正重要的操作都在__release_stripe函数中。

2.5.1 __release_stripe
=======================
     首先会判断sh的引用计数sh->count，如果它减小到0则说明所有对sh的操
     作都完成了，需要唤醒守护进程进行下一步的处理。
     我们记得，在前面调用过的init_stripe函数中有这样一行语句：
     BUG_ON(atomic_read(&sh->count) != 0);
     就是说一开始获取到的sh，引用计数肯定是0，然后，在
     get_active_stripe函数的的末尾处，会执行这样一行语句：
     atomic_inc(&sh->count);
     将sh的引用计数加1。
     对于stripe0共进行了3次4k数据的读写，每次进入get_active_stripe函数
     后，会让sh->count加1，进入__release_stripe函数后，又将其减到0。
     然后检测sh->state，目前sh->state的值应该是0x00000004，只有
     STRIPE_HANDLE被置位（在make_request函数调用add_stripe_bio之后，调
     用release_stripe函数之前）。因此在条件判断中会进入这一行：
     list_add_tail(&sh->lru, &conf->handle_list);
     将stripe挂在handle_list链表上。
     然后执行：
     md_wakeup_thread(conf->mddev->thread);
     唤醒raid5d守护线程。
     虽然守护线程会在这里被唤醒，但并不会马上执行。实际上，除非
     make_request函数由于sh耗尽而进入休眠，否则在它返回之前raid5d线程
     是一直都得不到机会执行的。所以，当写入stripe0的3块4k数据都执行
     过__release_stripe之后，再等到make_request函数返回或进入休
     眠，raid5d线程会开始执行，提交到strpe0的数据会得到进一步处理。

3 raid5d
#########
  raid5d线程开始执行后，会进入一个大循环，这个循环中，首先调
  用__get_priority_stripe函数获取一个需要处理的sh，然后调用
  handle_stripe函数对这个sh进行处理，最后调用release_stripe函数来决定
  是否要再次唤醒raid5d线程，或是把sh释放掉。一直等到所有的sh都处理完
  了，才退出循环。在raid5d的最后会调用async_tx_issue_pending_all函数，
  如果在处理过程中有进行dma操作的话，这个函数会确保dma开始运行。

3.1 __get_priority_stripe
^^^^^^^^^^^^^^^^^^^^^^^^^^
   这个函数会尝试从handle_list和hold_list两个链表上获取sh，对于写操作
   来说，如果一个sh已经是整条带写，那么它会被挂在handle_list上，否则就
   会挂在hold_list上。所以总是优先搜索handle_list，如果有整条带写，就
   先处理。等到整条带写的都处理完了，可能已经又有新的写操作提交进来，
   让那些之前不是整条带写的sh也变成整条带写了。这样可以提高性能。
   在这里，将stripe0的sh从handle_list上取下来，然后给sh->count加1。通
   常，把sh放到链表上的操作都是在release_stripe函数里完成的。而
   release_stripe函数只有将sh->count减到0才会把它挂到某个链表上。所以，这
   里给sh->count加1后，结果总是1。

3.2 handle_stripe
^^^^^^^^^^^^^^^^^^
   通过__get_priority_stripe函数获取到sh之后，接下来就是调用
   handle_stripe来处理这个sh。handle_stripe判断这个sh的raid等级来调相
   应的处理函数。

3.2.1 handle_stripe5
~~~~~~~~~~~~~~~~~~~~~
    首先循环查询一遍每个dev的flag，根据flag的状态设置相应的变量。对于
    stripe0的sh，它的dev0 dev1 dev2对应的flag都是0x04，dev3对应的flag
    是0x00。即，0，1，2三块盘的R5_OVERWRITE被置位。
    循环结束后还要进行许多的状态判断，用来确定这个sh究竟要执行哪些操作。
    最终，实际会被调用到的是handle_stripe_dirtying5函数。

3.2.1.1 handle_stripe_dirtying5
================================
     对于一次写操作，该函数用来判断是要使用rcw还是rmw。比如在一个
     stripe中我只写1块盘。那么我可以通过把要写的这块盘的数据与校验盘的
     数据读回，与新的数据做异或，得出校验数据，这就是rmw。我也可以把所
     有其他盘的数据读回，与新写入的数据做异或，算出校验数据，这就是rcw。
     该函数统计出使用rcw与rmw两种操作时所需的读盘次数，哪种操作需要读
     盘的次数少，就采用哪种操作。
     对于整条带写，肯定是使用rcw，因为一次读盘操作都不需要。

3.2.1.1.1 schedule_reconstruction
----------------------------------
      对于一次回读都不需要的情况，还需调用schedule_reconstruction函数
      来设置一些状态标志。
      对于我们的整条带写操作，会进行如下的设置：
      sh->reconstruct_state = reconstruct_state_drain_run;
      set_bit(STRIPE_OP_BIODRAIN, &s->ops_request);
      set_bit(STRIPE_OP_RECONSTRUCT, &s->ops_request);

3.2.1.2 raid_run_ops
=====================
     接下来，handle_stripe5函数会调用raid_run_ops函数来进行xor运算。在
     raid5.c中有如下宏定义：
     #define raid_run_ops __raid_run_ops
     所以，实际调用的函数是__raid_run_ops。
     该函数首先用memcpy把bio中的数据拷贝到sh的buffer中，然后对sh的
     buffer中的数据进行xor计算。如果硬件支持memcpy和xor操作的话，这些
     操作将会异步进行。在完成后调用callback函数，callback函数中会调用
     release_stripe，以便在适当的时候唤醒raid5d线程进行后续的处理。

3.2.1.3 handle_stripe5结束
===========================
     我们假设使用异步的硬件dma进行memcpy和xor运算，那么，对于整条带的写
     操作，handle_stripe5接下来不会再进行什么实质性的操作了。直到硬件
     操作完成，再次唤醒raid5d后才会处理。

3.3 release_stripe
^^^^^^^^^^^^^^^^^^^
   在raid5d中调用完handle_stripe后，回再次调用release_stripe。由于在
   ops_run_reconstruct5函数中执行了：
   atomic_inc(&sh->count);
   此时sh->count的值是2，减1后得1，不是0，所以不会进行任何操作，直接退
   出。

4 ops_complete_reconstruct
###########################
  memcpy与xor操作都完成后，会调用ops_complete_reconstruct函数。该函数
  会再次调用release_stripe函数，进入release_stripe函数时，sh->count的
  值是1，减1后成为0。因此会再次唤醒raid5d线程。

5 再次进入raid5d
#################
  与第一次执行raid5d一样，依然是先获取sh，调用handle_stripe处理sh，最
  后调用release_stripe。只是这次进入handle_stripe5函数后，会调用
  ops_run_io函数将计算完的校验数据与上层通过make_request传递下来的数据
  一起写入磁盘。

5.1 ops_run_io
^^^^^^^^^^^^^^^
   第一次调用handle_stripe函数的时候也会进入ops_run_io，只是当时
   R5_Wantwrite标志和R5_Wantread都没有被设置，所以不会进行任何操作。然
   而在ops_complete_reconstruct函数中，sh->reconstruct_state的值会被设
   置成reconstruct_state_drain_result。这样，在handle_stripe5函数中，
   就会将所有需要执行写入操作的dev的flag置上R5_Wantwrite标志。
   ops_run_io通过这个标志判断那块盘需要执行写操作。没执行一次写操作前，都
   会把sh->count的值加1。每执行完一块盘的写操作，就会调用一次回调函数
   raid5_end_write_request。该函数会调用release_stripe函数，而
   release_stripe函数会将sh->count的值减1，并检测sh->count是不是已经减
   到0了。。这样，当最后一次写操作完成后，release_stripe函数中会发现
   sh->count的值减到0了，于是第三次唤醒raid5d线程。

6 raid5_end_write_request
##########################
  每一次写磁盘完成后调用，设置一些标志位，并调用release_stripe函数，当
  最后一个写操作完成后，release_stripe函数会唤醒raid5d守护线程。

7 第三次进入raid5d
###################
  与前两次一样，依然是先获取sh，然后处理sh，最后release sh，只是这次在
  handle_stripe5函数中会调用handle_stripe_clean_event函数。

7.1 handle_stripe_clean_event
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   当一个sh处理完成后，调用该函数设置一些相应的状态。

7.2 release_stripe
^^^^^^^^^^^^^^^^^^^
   sh处理完成，将其挂到inactive_list链表上，并将active_stripes减一。