IO调度程序

虽然块设备驱动程序一次可以传送一个单独的扇区，但是块IO层通常不会为磁盘上每个被访问的扇区都单独执行一次IO操作；这会导致磁盘性能的下降，因为确定磁盘表面上扇区的物理位置是相当费时的。取而代之的是，只要有可能，内核就试图把几个扇区合并在一起，并作为一个整体来处理，这样就减少了磁头的平均移动时间。

 

当内核组件要读或写一些磁盘数据时，实际上创建一个块设备请求。从本质上说，请求描述的是所请求的扇区以及要对它执行的操作类型（读或写）。然而并不是请求一发出，内核就满足它——IO操作仅仅被调度，执行会向后推迟。当请求传送一个新的数据块时，内核检查能否通过稍微扩展前一个一直处于等待状态的请求而满足新请求（也就是说，能否不用进一步的寻道操作就能满足新请求）。由于磁盘的访问大都是顺序的，因此这种简单机制会高效很多。

 

延迟请求复杂化了块设备的处理。请求数据的进程有可能被挂起。然而，块设备驱动程序本身不会被阻塞，因为试图访问同一磁盘的任何其他进程也可能被阻塞。为了防止块设备驱动程序被挂起，每个IO操作都是异步处理的。特别是块设备驱动程序是中断驱动的：通用块层调用IO调度程序产生一个新的块设备请求或扩展一个已有的块设备请求，然后终止。随后激活的块设备驱动程序会调用一个所谓的策略例程(strategy routine，一个驱动程序实现的最主要的函数，完成对实际的块设备控制器的操作)选择一个待处理的请求，并向磁盘控制器发出一条适当的命令来满足这个请求。当IO操作终止时，磁盘控制器就产生一个中断，如果需要，相应的中断处理程序就又调用策略例程去处理队列中的另一个请求。

 

每个快设备驱动程序都维持着自己的请求队列，它包含设备待处理的请求链表。如果磁盘控制器正在处理几个磁盘，那么通常每个物理磁盘（不是分区）都有一个请求队列。在每个请求队列上单独执行I/O调度，这样可以提高磁盘的性能。

 

请求队列描述符

请求队列是由一个大的数据结构request_queue表示的，其定义如下：

---------------------------------------------------------------------

include/linux/blkdev.h

328 struct request_queue

329 {

330         /*

331          * Together with queue_head for cacheline sharing

332          */

            /* 待处理的请求的链表 */

333         struct list_head        queue_head;

            /* 指向队列中首个可能合并的请求描述符 */

334         struct request          *last_merge;

            /* 指向elevator对象（调度算法）的指针 */

335         struct elevator_queue   *elevator;

336

337         /*

338          * the queue request freelist, one for reads and one for

339          * writes */

            /* 为分配请求描述符所使用的数据结构 */

340         struct request_list     rq;

341         /* 实现驱动程序的策略例程入口点的方法 */

342         request_fn_proc         *request_fn;

        /* 将一个新请求插入请求队列时调用的方法 */

343         make_request_fn         *make_request_fn;

        /* 该方法把这个处理请求的命令发送给硬件设备 */

344         prep_rq_fn              *prep_rq_fn;

        /* 去掉块设备时调用的方法 */

345         unplug_fn               *unplug_fn;

/* 当增加一个新段时，该方法返回可插入到某个已存在的bio结构中

* 的字节数*/

346         merge_bvec_fn           *merge_bvec_fn;

347         prepare_flush_fn        *prepare_flush_fn;

348         softirq_done_fn         *softirq_done_fn;

349         rq_timed_out_fn         *rq_timed_out_fn;

350         dma_drain_needed_fn     *dma_drain_needed;

351         lld_busy_fn             *lld_busy_fn;

352

353         /*

354          * Dispatch queue sorting

355          */

356         sector_t                end_sector;

357         struct request          *boundary_rq;

358

359         /*

360          * Auto-unplugging state

361          */

            /* 插入设备时使用的动态定时器 */

362         struct timer_list       unplug_timer;

363         int        unplug_thresh;  /* After this many requests */

364         unsigned long  unplug_delay; /* After this many jiffies */

365         struct work_struct      unplug_work;

366

367         struct backing_dev_info backing_dev_info;

368

369         /*

370          * The queue owner gets to use this for whatever they like.

371          * ll_rw_blk doesn't touch it.

372          */

373         void                    *queuedata;

374

375         /*

376          * queue needs bounce pages for pages above this limit

377          */

378         gfp_t                   bounce_gfp;

379

380         /*

381          * various queue flags, see QUEUE_* below

382          */

383         unsigned long           queue_flags;

384

385         /*

386          * protects queue structures from reentrancy. ->__queue_lock

387          * should _never_ be used directly, it is queue private.

388          * always use ->queue_lock.

389          */

390         spinlock_t              __queue_lock;

391         spinlock_t              *queue_lock;

392

393         /*

394          * queue kobject

395          */

---------------------------------------------------------------------

实质上，请求队列是一个双向链表，其元素就是请求描述（也就是request数据结构）。请求队列描述符中的queue_head字段存放链表的头，而请求描述符中queuelist字段的指针把任一请求链接到链表的前一个和后一个元素之间。队列链表中元素排列方式对每个块设备驱动程序是特定的；然而，I/O调度程序提供了几种预先确定好的元素排列顺序。

 

backing_dev_info字段是一个backing_dev_info类型的小对象，它存放了关于基本硬件块设备的I/O数据流量的信息。

 

请求描述符

每个块设备的待处理请求都是用一个请求描述符来表示的，请求描述符定义如下：

---------------------------------------------------------------------

include/linux/blkdev.h

158 struct request {

159   struct list_head queuelist;

160   struct call_single_data csd;

161

162   struct request_queue *q;

163

164   unsigned int cmd_flags;

165   enum rq_cmd_type_bits cmd_type;

166   unsigned long atomic_flags;

167

168   int cpu;

169

170   /* the following two fields are internal, NEVER access directly */

171   unsigned int __data_len;        /* total data len */

172   sector_t __sector;              /* sector cursor */

173

174   struct bio *bio;

175   struct bio *biotail;

176

177   struct hlist_node hash; /* merge hash */

178   /*

179    * The rb_node is only used inside the io scheduler, requests

180    * are pruned when moved to the dispatch queue. So let the

181    * completion_data share space with the rb_node.

182    */

183   union {

184           struct rb_node rb_node; /* sort/lookup */

185           void *completion_data;

186   };

187

188   /*

189    * two pointers are available for the IO schedulers, if they

190    * need more they have to dynamically allocate it.

191    */

192   void *elevator_private;

193   void *elevator_private2;

194

195   struct gendisk *rq_disk;

196   unsigned long start_time;

197

198   /* Number of scatter-gather DMA addr+len pairs after

199    * physical address coalescing is performed.

200    */

201   unsigned short nr_phys_segments;

202

203   unsigned short ioprio;

204

205   int ref_count;

206

207   void *special;   /* opaque pointer available for LLD use */

208   char *buffer;  /* kaddr of the current segment if available */

209

210   int tag;

211   int errors;

212

213   /*

214    * when request is used as a packet command carrier

215    */

216   unsigned char __cmd[BLK_MAX_CDB];

217   unsigned char *cmd;

218   unsigned short cmd_len;

219

220   unsigned int extra_len; /* length of alignment and padding */

221   unsigned int sense_len;

222   unsigned int resid_len; /* residual count */

223   void *sense;

224

225   unsigned long deadline;

226   struct list_head timeout_list;

227   unsigned int timeout;

228   int retries;

229

230   /*

231    * completion callback.

232    */

233   rq_end_io_fn *end_io;

234   void *end_io_data;

235

236   /* for bidi */

237   struct request *next_rq;

238 };

---------------------------------------------------------------------

每个请求包含一个或多个bio结构。最初，通用块层创建一个仅包含一个bio结构的请求。然后，I/O调度要么向初始的bio中增加一个新段，要么将另外一个bio结构链接到请求中，从而“扩展”该请求。可能存在新数据与请求中已存在的数据物理相邻的情况。请求描述符的bio字段指向请求中的第一个bio结构，而biotail字段则指向最后一个bio结构。__rq_for_each_bio(_bio, rq)宏执行一个循环，从而遍历请求中的所有bio结构。

 

请求描述符中的几个字段值可能是动态变化的。例如，一旦bio中引用的数据传送完毕，bio字段立即更新从而指向请求链表中的下一个bio。在此期间，新的bio可能被加入到请求链表的尾部，所以biotail的值也可能改变。

 

当磁盘数据块正在传送时，请求描述符的其它几个字段的值有I/O调度程序或设备驱动程序修改。例如，nr_sectors存放整个请求还需传送的扇区数，current_nr_sectors存放当前bio结构中还需要传送的扇区数。

 

flags中存放了很多标志，如下所示。最重要的一个标志是REQ_RW，它确定数据传送方向。

REQ_RW     数据传送的方向：设置时，为读，不设置，为写

REQ_FAILFAST_DEV  万一出错请求申明不再重试I/O操作

REQ_FAILFAST_TRANSPORT   万一出错请求申明不再重试I/O操作

REQ_FAILFAST_DRIVER  万一出错请求申明不再重试I/O操作

REQ_DISCARD   请求丢弃扇区

REQ_SORTED elevator knows about this request

REQ_SOFTBARRIER   may not be passed by ioscheduler

REQ_HARDBARRIER   may not be passed by drive either

REQ_FUA    forced unit access

REQ_NOMERGE   申明不合并请求

REQ_STARTED   drive already may have started this one

REQ_DONTPREP  don't call prep for this one

REQ_QUEUED uses queueing

REQ_ELVPRIV   elevator private data attached

REQ_FAILED 当请求失败时设置该标志

REQ_QUIET  万一I/O操作出错请求申明不产生内核消息

REQ_PREEMPT   set for "ide_preempt" requests

REQ_ORDERED_COLOR   is before or after barrier

REQ_RW_SYNC   请求是同步的（同步读或写）

REQ_ALLOCED   请求来自于分配池

REQ_RW_META   metadata io request

REQ_COPY_USER 含有用户页的拷贝

REQ_INTEGRITY   integrity metadata has been remapped

REQ_NOIDLE    Don't anticipate more IO after this one

REQ_IO_STAT   account I/O stat

REQ_MIXED_MERGE   merge of different types, fail separately

 

队请求描述符的分配进行管理

在重负载和磁盘操作频繁的情况下，固定数目的动态空闲内存将成为进程想要把请求加入请求队列q的瓶颈。为了解决这个问题，每个request_queue描述包含一个request_list数据结构，其定义为：

---------------------------------------------------------------------

include/linux/blkdev.h

40 struct request_list {

 41         /*

 42          * count[], starved[], and wait[] are indexed by

 43          * BLK_RW_SYNC/BLK_RW_ASYNC

 44          */

 45         int count[2];

 46         int starved[2];

 47         int elvpriv;

 48         mempool_t *rq_pool;

 49         wait_queue_head_t wait[2];

 50 };

---------------------------------------------------------------------

count字段，用于记录分配给READ和WRITE请求的请求描述符数。

wait字段，分别存放了为获得空闲的读和写请求描述符而睡眠的进程

rq_pool字段，指向请求描述符的内存池

 

blk_get_request()函数试图从一个特定请求队列的内存池（也就是上面request_list结构成员的rq_pool字段所引用的）中获得一个空闲的请求描述符；如果内存区不足并且内存池已经用完，则要么挂起当前进程，要么返回NULL（如果不能阻塞内核控制路径）。如果分配成功，则将请求队列的request_list结构的地址存放在请求描述符的rl字段中。blk_put_request()函数则释放一个请求描述符；如果该描述符的引用计数器的值为0，则将描述符归还回它原来所在的内存池。