精华内容
下载资源
问答
  • 通用块层IO调度算法之deadline算法

    千次阅读 2016-12-10 11:08:46
    在讲通用块层IO调度算法之前,我们先来回顾一下page是如何进入通用块层的,在文件系统中的writeback机制中,回写线程先将page变成buffer head,然后submit_bh函数又将buffer head变成了bio,最后调用submit_bio函数...
    在讲通用块层IO调度算法之前,我们先来回顾一下page是如何进入通用块层的,以ext4文件系统为例,在ext4文件系统中的writeback机制中,回写线程先将page变成buffer head,然后submit_bh函数又将buffer head变成了bio,最后调用submit_bio函数进入通用块层,在submit_bio函数中会调用一个通用的函数 make_request_fn将bio提交,在块设备层中make_request_fn是指向blk_queue_bio函数的,通过blk_queue_bio函数才真正进入了IO调度。
    言归正传,我们来聊聊deadline算法,deadline算法是为了解决Noop算法带来的饥饿问题,核心思想是把每一个请求设置一个期限,超时就尽快处理,在linux/block/deadline-iosched.c文件中内核定义了一个核心数据结构deadline_data
    struct deadline_data {
    	/*
    	 * run time data
    	 */
    
    	/*
    	 * requests (deadline_rq s) are present on both sort_list and fifo_list
    	 */
    	struct rb_root sort_list[2];	
    	struct list_head fifo_list[2];
    
    	/*
    	 * next in sort order. read, write or both are NULL
    	 */
    	struct request *next_rq[2];
    	unsigned int batching;		/* number of sequential requests made */
    	unsigned int starved;		/* times reads have starved writes */
    
    	/*
    	 * settings that change how the i/o scheduler behaves
    	 */
    	int fifo_expire[2];
    	int fifo_batch;
    	int writes_starved;
    	int front_merges;
    };
    

    这些字段我一个个来解释,deadline算法定义了两类队列,每类队列又分为读队列和写队列,一类队列就是sort_list,对请求按起始扇区进行排序,用红黑树来组织(rb_root是红黑树的根节点);另一类是fifo_list,就是一个简单的先进先出队列,自然是通过到达时间排序,用循环双向链表list_head组织。然后next_rq代表下一个读/写请求。剩下的字段
    用两个机制说明
    1. 批量dispatch
    deadline算法是在读写方向确定后,将请求一批一批地dispatch,fifo_batch字段定义了批量发送的最大值为16,batching表示当前的发送数,当batching小于16的时候,请求会连续地发送,大于或等于16的时候(batching从0开始所以是0-15)就会启动下一轮批量dispatch。
    2. 写请求饥饿线
    对于读请求和写请求,内核对它们的处理方式是不一样的,内核对读请求很偏心,fifi_expire这个数组分别存储了读/写请求的期限,读请求是500ms,写请求是5s,不仅如此,即使写请求超时也不一定立即响应,而是等到读请求当前的批次大于写请求饥饿线的时候才去处理写请求,内核如此做是因为读请求是同步的,会阻塞进程,所以必须马上处理,而写请求是异步的,进程可以先去干其它事情,所以实时性要求不高。在deadline_data结构体中,starved表示读请求当前批次,writes_starved表示写请求饥饿线,默认为2。还有一个front_merges字段表示能否进行前向合并的检查。
    deadine_data的初始化如下
    static const int read_expire = HZ / 2;  /* max time before a read is submitted. */
    static const int write_expire = 5 * HZ; /* ditto for writes, these limits are SOFT! */
    static const int writes_starved = 2;    /* max times reads can starve a write */
    static const int fifo_batch = 16;       /* # of sequential requests treated as one
    				     by the above parameters. For throughput. */
    INIT_LIST_HEAD(&dd->fifo_list[READ]);
    INIT_LIST_HEAD(&dd->fifo_list[WRITE]);
    dd->sort_list[READ] = RB_ROOT;          //红黑树的根节点,初始化为NULL, #define RB_ROOT (struct rb_root) { NULL, }
    dd->sort_list[WRITE] = RB_ROOT;
    dd->fifo_expire[READ] = read_expire;
    dd->fifo_expire[WRITE] = write_expire;
    dd->writes_starved = writes_starved;
    dd->front_merges = 1;
    dd->fifo_batch = fifo_batch;
    接下来具体分析相关的函数
    首先是将bio封装成请求,如何构造请求呢,首先如果能将bio合并到当前某个请求,那自然就不用新建
    所以内核会通过elv_merge调用e->type->ops.elevator_merge_fn函数,而这个函数在deadline算法中定义为deadline_merge函数
    static int
    deadline_merge(struct request_queue *q, struct request **req, struct bio *bio)
    {
    	struct deadline_data *dd = q->elevator->elevator_data;
    	struct request *__rq;
    	int ret;
    
    	/*
    	 * check for front merge
    	 */
    	if (dd->front_merges) {  //如果可以进行前向合并
    		sector_t sector = bio_end_sector(bio);  //找到bio的结束扇区号
    		//如果能找到一个请求,它的起始扇区号和sector相同(就是连续的)
    		__rq = elv_rb_find(&dd->sort_list[bio_data_dir(bio)], sector);
    		if (__rq) {
    			BUG_ON(sector != blk_rq_pos(__rq));
    			//进行合并,然后成功返回ret,表示前向合并完成
    			if (elv_rq_merge_ok(__rq, bio)) {
    				ret = ELEVATOR_FRONT_MERGE;
    				goto out;
    			}
    		}
    	}
    
    	return ELEVATOR_NO_MERGE;
    out:
    	*req = __rq;
    	return ret;
    }
    
    然后还要再检查这个合并了的请求能否再和其它请求合并,合并了再做善后工作,使用deadline_merged_requests函数
    static void
    deadline_merged_requests(struct request_queue *q, struct request *req,
    			 struct request *next)
    {
    	/*
    	 * if next expires before rq, assign its expire time to rq
    	 * and move into next position (next will be deleted) in fifo
    	 */
    	if (!list_empty(&req->queuelist) && !list_empty(&next->queuelist)) {
    		if (time_before(next->fifo_time, req->fifo_time)) { //如果next的期限小于req
    			list_move(&req->queuelist, &next->queuelist);  //这个queuelist实际上就是真正发给设备驱动程序的队列,处理完了的队列
    			req->fifo_time = next->fifo_time;   //因为是next比req要先响应,合并完了肯定要以先响应的为准
    		}
    	}
    
    	/*
    	 * kill knowledge of next, this one is a goner
    	 */
    	deadline_remove_request(q, next);  //从fifo_list和sort_list删除next
    }
    然后还得做一些善后工作,deadline_merged_requests函数主要是把合并了的请求从sort_list删除再加入
    static void deadline_merged_request(struct request_queue *q,
    				    struct request *req, int type)
    {
    	struct deadline_data *dd = q->elevator->elevator_data;
    
    	/*
    	 * if the merge was a front merge, we need to reposition request
    	 */
    	if (type == ELEVATOR_FRONT_MERGE) {
    		elv_rb_del(deadline_rb_root(dd, req), req);
    		deadline_add_rq_rb(dd, req);
    	}
    }
    到这终于合并完请求了,接下来是加入请求,通过blk_queue_bio调用__elv_add_request,__elv_add_request函数又调用q->elevator->type->ops.elevator_add_req_fn,这个函数在deadline算法中被定义为deadline_add_request
    /*
     * add rq to rbtree and fifo
     */
    static void
    deadline_add_request(struct request_queue *q, struct request *rq)
    {
    	struct deadline_data *dd = q->elevator->elevator_data;
    	const int data_dir = rq_data_dir(rq); // 获取请求的方向(direction),读/写
    
    	deadline_add_rq_rb(dd, rq);  //加入sort_list,rb是readblack的缩写,也就是红黑树
    
    	/*
    	 * set expire time and add to fifo list
    	 */
    	rq->fifo_time = jiffies + dd->fifo_expire[data_dir];  //jiffies是系统全局变量
    	list_add_tail(&rq->queuelist, &dd->fifo_list[data_dir]);   //将rq加入fifo_list
    } 
    再看deadline_add_rq_rb这个函数
    static inline struct rb_root *
    deadline_rb_root(struct deadline_data *dd, struct request *rq)
    {
    	return &dd->sort_list[rq_data_dir(rq)];
    }
    
    static void
    deadline_add_rq_rb(struct deadline_data *dd, struct request *rq)
    {
    	//获取sort_list中指向根节点的指针root,因为从rb_node开始才是正式的红黑树,root只是指向根节点的指针
    	struct rb_root *root = deadline_rb_root(dd, rq);
    	
    	//这个函数会把rq的rb_node指针指向sort_list的一个节点,也就是把每个请求与sort_list关联
    	elv_rb_add(root, rq);
    }

    最后是dispatch请求

    static int deadline_dispatch_requests(struct request_queue *q, int force)
    {
    	struct deadline_data *dd = q->elevator->elevator_data;
    	const int reads = !list_empty(&dd->fifo_list[READ]);
    	const int writes = !list_empty(&dd->fifo_list[WRITE]);
    	struct request *rq;
    	int data_dir;
    
    	/*
    	 * batches are currently reads XOR writes
    	 */
    	if (dd->next_rq[WRITE]) 
    		rq = dd->next_rq[WRITE];
    	else
    		rq = dd->next_rq[READ];
    
    	//如果有rq并且批量dispatch未到上限,则直接进行dispatch
    	if (rq && dd->batching < dd->fifo_batch)
    		/* we have a next request are still entitled to batch */
    		goto dispatch_request;
    
    	/*
    	 * at this point we are not running a batch. select the appropriate
    	 * data direction (read / write)
    	 */
    
    	if (reads) {
    		BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[READ]));
    		//触发写请求饥饿线,必须处理写请求了
    		if (writes && (dd->starved++ >= dd->writes_starved))
    			goto dispatch_writes;
    		//同时把请求方向变为写
    		data_dir = READ;
    
    		goto dispatch_find_request;
    	}
    
    	/*
    	 * there are either no reads or writes have been starved
    	 */
    
    	if (writes) {
    dispatch_writes:
    		BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE]));
    
    		dd->starved = 0;
    
    		data_dir = WRITE;
    
    		goto dispatch_find_request;
    	}
    
    	return 0;
    
    dispatch_find_request:
    	/*
    	 * we are not running a batch, find best request for selected data_dir
    	 */
    	//如果fifo_list有超时或者下一个请求的方向变了,就去fifo_list取request,然后还得执行下面的dispatch_request
    	if (deadline_check_fifo(dd, data_dir) || !dd->next_rq[data_dir]) {
    		/*
    		 * A deadline has expired, the last request was in the other
    		 * direction, or we have run out of higher-sectored requests.
    		 * Start again from the request with the earliest expiry time.		 */
    		rq = rq_entry_fifo(dd->fifo_list[data_dir].next); 
    	} else { // 为什么这里可以直接从fifo_list取而不是sort_list,因为最终都需要通过rq的rb_node到sort_list找
    		/*
    		 * The last req was the same dir and we have a next request in
    		 * sort order. No expired requests so continue on from here.
    		 */
    		rq = dd->next_rq[data_dir]; //否则接着取请求
    	}
    
    	dd->batching = 0; //表示启动新一批请求dispatch
    
    dispatch_request:
    	/*
    	 * rq is the selected appropriate request.
    	 */
    	dd->batching++;
    	deadline_move_request(dd, rq); //从fifo_list和sort_list中删除,再加入req->queuelist中,这里就从IO调度层离开了
    
    	return 1;
    }
    









    展开全文
  • 通用块层抽象  通用块层位于scsi的上层,文件系统的下层,系统主要的内存管理和读写优化都是在这里完成的。DIRECT_IO是跳过这一层的。这一层不是驱动,而是一种机制。其代码位于linux/block文件夹内,是单列出来的...

    通用块层抽象

             通用块层位于scsi的上层,文件系统的下层,系统主要的内存管理和读写优化都是在这里完成的。DIRECT_IO是跳过这一层的。这一层不是驱动,而是一种机制。其代码位于linux/block文件夹内,是单列出来的。

             我们先不看代码,分析一下这一层都需要什么组件。

    l  对磁盘的抽象genhd.c和对分区的抽象:partition-generic.c和partitions目录下的文件

    l  上层文件系统会把对文件访问转变为对多个sector的访问,这些sector很可能在内存中是分离的。所以需要一种数据表示方法,用来表示要读写的数据内容。这这个数据结构叫做bio(很奇怪的是这里为什么不直接使用scsi使用的scatterlist?)

    l  scsi相关

    n  新的scsi标准有DIF/DIX的数据保护机制,无论对于读还是写的数据,都需要一个数据完整性的校验,由于在通用块层存储数据的结构体是bio,所以对其进行校验的文件叫做bio-integraty.c。这个文件完成的是与内存相关的设置,真正的算法在blk-integraty.c中定义的一系列钩子函数。不同的硬件会注册不同的计算方法供本层调用。也就是说,这里实际实现的是DIX协议。

    n  本层要知道scsi的接口,本层定义了bsg(blockSCSI generic device)的v4接口,在bsg.c和bsg-lib.c

    n  t10保护的支持算法t0-pi.c,scsi的ioctl:scsi_ioctl.c

    l  连接本层各个功能组件的核心程序:blk-core.c,还包括一些辅助文件实现些特定的周边。这一部分包括

    n  内核执行这部分代码不是阻塞的,而是使用内核线程完成的,使用的是kblockd,其定义和相关功能位于blk-core.c中

    n  request的处理(bio只是数据的存储结构,但是一个命令请求不只有数据,还需要有其他控制和状态信息,这些信息和bio一起被组织到request中),但是要注意的是request和bio都只是本层的数据结构,request服务于电梯算法,bio用于盛放用户传进内核的数据

    u  将用户数据映射到bio结构体的blk-map.c

    u  将request中的bio数据映射到下层(scsi)使用的scatterlist结构体的处理程序blk-merge.c

    u  request如果超过了一定的时间需要被time out掉,代码在blk-timeout.c

    u  request请求到的数据在本层需要有缓冲,可以从中提取提交到上层上层所需要的数据,而丢弃或者缓存一部分上层没有要到的数据。这种行为叫做bounce,功能定义在bounce.c中

    n  队列(queue)处理(对于块设备的一系列命令,需要队列缓存,并且这一层最重要的,队列中的各个命令有可能可以合并为一个,例如读取连续的数据的两个命令,由于每次存取数据的量越大,越节省时间,所以这一步是提高效率的关键)

    u  linux的设计者将对queue的插入执行操作单独的提取出来放到blk-exe.c中

    u  对队列的属性进行设置的blk-settings.c

    u  对队列中的request添加ID(tag),可以通过该tag直接找到该request,实现在blk-tag.c

    u  凡是通信管道都要考虑流量控制问题。queue可以有多个来源,如果某个来源瞬间提交了过多的bio,那么其他来源的bio就可能饥饿。防止这种现象发生需要给队列针对某一个来源添加一个阈值,这个阈值的控制在blk-throttle.c

    n  电梯算法接口。上一条说的合并多个request的操作,需要有合并的算法,合并的算法有很多,但是核心部分要为这些算法提供调用的接口函数

    n  提交请求。当电梯算法被执行完,多个request和其对应的bio被合并,这个bio就需要被提交到下层(scsi的上层)去实际的执行发送。发送完毕还要执行回调。这部分代码也在这里提供。

    l  电梯算法:电梯算法在queue上执行合并操作,是性能优化的关键。代码位于elevator.c,deadline-iosched.c,cfq-iosched.c,noop-iosched.c,还有提供优先级的ioprio.c

    l  对于IO上下文的处理。IO上下文是在request上层的数据结构,如果说通用块层处理的request级别的数据结构,文件系统就是处理的IO上下文。而文件系统层次包括同步和异步两种数据模式,这里的IO上下文(io_context)主要是用在异步,异步IO在提交IO请求前必须要初始化一个IO上下文,一个IO上下文会包含多个request。通用块层对IO上下文的处理函数放在blk-ioc.c。

    l  正常的逻辑是发送了IO命令,命令请求完毕后会调用回调函数。但是,通用块层允许poll操作,就是没有回调函数,请求执行完后需要用户手动查询和处理。这部分代码在blk-iopoll.c

    l  对本层命令队列的处理可以有一个CPU,也可以有多个。如果多个,就需要对队列进行特殊的优化,叫mq,相关代码位于blk-mq.c、blk-mq-cpu.c、blk-mq-cpumap.c、blk-mq.h、blk-mq-sysfs.c、blk-mq-tag.c、blk-mq-tag.h中

    l  内核处理命令的返回结果,在通用块层不可能是使用硬中断,所以这里的回调使用的是软中断,定义在blk-softirq.c

    l  实现sysfs接口,定义在blk-sysfs.c,实现cgroup子系统的blk-cgroup.c

    l  其他的辅助功能组件:将内容flush进磁盘的blk-flush.c、辅助函数blk-lib.c、用来解析磁盘信息返回值的cmdline-parser.c、提供ioctl接口的compat_ioctl.c,ioctl.c

    l   

     

     

    从以上可以看出,这一部分的关键组件是:request、queue、bio、elevator和磁盘与分区的抽象。

     

     

     

     

     

     

     

     

     

     

     

     


    数据完整性校验

             如果要对bio进行数据完整性校验,需要调用bio_integraity_alloc给bio分配对应的空间,之后通过bio_integraty_add_page给bio添加额外的空间,用bio_free就会自动删除掉分配的空间。

             具体的计算bip(dif)的算法由具体的驱动提供,驱动调用的是blk_integraty_register来注册自己的计算函数。

             在文件系统中,可以通过/sys/block/<bdev>/integraty/目录下的write_generate和read_verify来控制是否执行读写校验。

             大部分情况下,数据完整性对于文件系统是透明的,但上层的文件系统仍可以显示的使用DIX。在bio_integraty_enabled为1的情况下,上层调用bio_integrity_prep为bio准备bip。

             磁盘设备在注册是可以生成blk_integrity结构体,体面就是存放具体的读写校验函数和tag的大小。

    设备抽象

    linux的通用快层对磁盘的抽象是gendisk结构体,该层以下的各种设备都是这个结构体的一种。例如scsi磁盘设备scsi_disk就是gendisk的一种。

    对于分区的抽象是structpartition。

    设备驱动抽象

     

     

     

     

    设备驱动操作抽象

    block_device_operations

     

    对设备进行驱动

    设备操作指令抽象

             对设备进行指令操作的结构体是struct request,连接通用快层和下层设备指令操作的数据结构是bio,bio在request中,被上层识别,也被下层识别。

    磁盘检测

    这部分描述当发现插入了磁盘或者是删除了磁盘时,内核是如何反应的。

    BIO和bio_set

             BIO是通用块层表达数据的方式,其将用户传递进来的数据转换为bio存储,bio又包含进了request。多个bio可以组成链接,bio中内生提供链表结构。

    struct bio {

             struct bio          *bi_next;        /*BIO 链表*/

             struct block_device *bi_bdev;    //文件系统层的块设备抽象

             unsigned long           bi_flags;   /* status, command, etc */

             unsigned long           bi_rw;                /* 标示是读还是写的标志位 */

     

             struct bvec_iter       bi_iter;

             unsigned int              bi_phys_segments;

     

             /*

              * To keep track of the max segment size, we account for the

              * sizes of the first and last mergeable segments in this bio.

              */

             unsigned int              bi_seg_front_size;

             unsigned int              bi_seg_back_size;

     

             atomic_t           bi_remaining;

     

             bio_end_io_t             *bi_end_io;    //BIO全部执行结束的回调函数

     

             void                    *bi_private;

             unsigned short                   bi_vcnt;    /* how many bio_vec's */

             unsigned short                   bi_max_vecs;  /* max bvl_vecs we can hold */

             atomic_t           bi_cnt;               /* pin count */

             struct bio_vec           *bi_io_vec;       /* the actual vec list */

             struct bio_set           *bi_pool;

     

             /*

              * We can inline a number of vecs at the end of the bio, to avoid

              * double allocations for a small number of bio_vecs. This member

              * MUST obviously be kept at the very end of the bio.

              */

             struct bio_vec           bi_inline_vecs[0];

    };

             内核里一个bio有多个bio_vec,一个bio_vec叫一个segment。由于上层提交来的bio中的bio_vec,所以bio本身也是可以合并的。但是每个queue可以有标志位QUEUE_FLAG_NO_SG_MERGE控制是否允许bio的合并。如此,bio就有了两种统计口径:bi_vcnt表示bio没有经过自身合并的bio_vec数目,bi_phys_segments表示将物理连续的bio_vec算成一个后统计出来的段总数。这里需要注意的是:bio的段总数并不是单个bio的段的数目,而因为bio天生是个链表,所以段的数目总是统计的是链表中段的总数。

    BIO标志

    BIO_SEG_VALID:bi_phys_segments有了有效值后置这个标志位。

    BIO操作

             bio_flagged(bio,flag)用于检测bio的bi_flags域是否与flag相等。

    request

             request中包含了bio和其他参数,例如表明携带数据总大小的__data_len。用双下划线的域一般是不直接使用,而是要使用辅助函数调用,典型的是blk_rq_bytes(const struct request *rq)函数返回这个值,而

    static inline unsigned intblk_rq_sectors(const struct request *rq)

    {

             returnblk_rq_bytes(rq) >> 9;

    }

    又可以返回这个request携带的sector的数目。

    struct request {

             struct list_head queuelist;

             union {

                       struct call_single_data csd;

                       unsigned long fifo_time;

             };

     

             struct request_queue *q;

             struct blk_mq_ctx *mq_ctx;

     

             u64 cmd_flags;

             enum rq_cmd_type_bits cmd_type;

             unsigned long atomic_flags;

     

             int cpu;

     

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

             unsigned int __data_len;         /* total data len */

             sector_t __sector;            /* sector cursor */

     

             struct bio *bio;

             struct bio *biotail;

     

             /*

              * The hash is used inside the scheduler, and killed once the

              * request reaches the dispatch list. The ipi_list is only used

              * to queue the request for softirq completion, which is long

              * after the request has been unhashed (and even removed from

              * the dispatch list).

              */

             union {

                       struct hlist_node hash;   /* merge hash */

                       struct list_head ipi_list;

             };

     

             /*

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

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

              * completion_data share space with the rb_node.

              */

             union {

                       struct rb_node rb_node; /* sort/lookup */

                       void *completion_data;

             };

     

             /*

              * Three pointers are available for the IO schedulers, if they need

              * more they have to dynamically allocate it.  Flush requests are

              * never put on the IO scheduler. So let the flush fields share

              * space with the elevator data.

              */

             union {

                       struct {

                                struct io_cq               *icq;

                                void                    *priv[2];

                       } elv;

     

                       struct {

                                unsigned int              seq;

                                struct list_head        list;

                                rq_end_io_fn            *saved_end_io;

                       } flush;

             };

     

             struct gendisk *rq_disk;

             struct hd_struct *part;

             unsigned long start_time;

    #ifdef CONFIG_BLK_CGROUP

             struct request_list *rl;              /* rl this rq is alloced from */

             unsigned long long start_time_ns;

             unsigned long long io_start_time_ns;    /* when passed to hardware */

    #endif

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

              * physical address coalescing is performed.

              */

             unsigned short nr_phys_segments;

    #if defined(CONFIG_BLK_DEV_INTEGRITY)

             unsigned short nr_integrity_segments;

    #endif

     

             unsigned short ioprio;

     

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

     

             int tag;

             int errors;

     

             /*

              * when request is used as a packet command carrier

              */

             unsigned char __cmd[BLK_MAX_CDB];

             unsigned char *cmd;

             unsigned short cmd_len;

     

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

             unsigned int sense_len;

             unsigned int resid_len;    /* residual count */

             void *sense;

     

             unsigned long deadline;

             struct list_head timeout_list;

             unsigned int timeout;

             int retries;

     

             /*

              * completion callback.

              */

             rq_end_io_fn *end_io;

             void *end_io_data;

     

             /* for bidi */

             struct request *next_rq;

    };

    struct list_head queuelist  BI  Organization on various internal

                        queues

     

    void *elevator_private      I   I/O scheduler private data

     

    unsigned char cmd[16]       D   Driver can use this for setting up

                        a cdb before execution, see

                        blk_queue_prep_rq

     

    unsigned long flags     DBI Contains info about data direction,

                        request type, etc.

     

    int rq_status           D   Request status bits

     

    kdev_t rq_dev           DBI Target device

     

    int errors          DB  Error counts

     

    sector_t sector         DBI Target location

     

    unsigned long hard_nr_sectors   B   Used to keep sector sane

     

    unsigned long nr_sectors    DBI Total number of sectors in request

     

    unsigned long hard_nr_sectors   B   Used to keep nr_sectors sane

     

    unsigned short nr_phys_segments DB  Number of physical scatter gather

                        segments in a request

     

    unsigned short nr_hw_segments   DB  Number of hardware scatter gather

                        segments in a request

     

    unsigned int current_nr_sectors DB  Number of sectors in first segment

                        of request

     

    unsigned int hard_cur_sectors   B   Used to keep current_nr_sectors sane

     

    int tag             DB  TCQ tag, if assigned

     

    void *special           D   Free to be used by driver

     

    char *buffer            D   Map of first segment, also see

                        section on bouncing SECTION

     

    struct completion *waiting  D   Can be used by driver to get signalled

                        on request completion

     

    struct bio *bio         DBI First bio in request

     

    struct bio *biotail     DBI Last bio in request

     

    struct request_queue *q     DB  Request queue this request belongs to

     

    struct request_list *rl     B   Request list this request came from

             结构体的定义都是和功能相关的。由于bio可以被合并进一个request,所以request要为这种功能提供支持。bio合并进request可以在原bio的前面合并也可能在后面。如果在前面,那么肯定是在最前面,此时直接利用bio本身的链表结构插入到最前面即可。如果在后面,也肯定是在最后面,但是此时没有使用bio本身的链表结构,而是使用了一个额外的域,叫biotail来盛放要合并进入的bio。因为这个域本身的定义就是用来放最后一个bio。向前合并最后一个bio不变,而向后合并最后一个bio要变化。

             request中的域分为3类,分别用在3个不同的地方:驱动、通用块层、IO调度。

     

    request标志

             REQ_FLUSH:表示执行bio前进行fluash。REQ_FUA表示执行bio后进行flush。

             QUEUE_FLAG_NO_SG_MERGE:表示是否允许bio本身的bio_vec进行物理合并。

    request_queue

    这是通用块层的请求队列,这个队列一个cpu一个。上层的数据请求首先生成bio,然后由bio生成request,然后添加到request_queue,然后request_queue会被执行。这个执行包括很多步骤,最重要的是电梯算法。每个算法都会在全局的request_queue之外生成自己的队列结构体elevator_queue。

    request_queue中有挂载的电梯算法的队列,并且还有为电梯算法服务的域。如last_merge表示上次合并的request。利用这个相当于cache,可以首先尝试看能不能与这个合并。因为连续数据的概率很大。

     

    struct request_queue {

             struct list_head        queue_head;

             struct request          *last_merge;

             struct elevator_queue     *elevator;

             int                       nr_rqs[2];         /* # allocated [a]sync rqs */

             int                       nr_rqs_elvpriv;         /* # allocated rqs w/ elvpriv */

             struct request_list  root_rl;

     

             request_fn_proc               *request_fn;

             make_request_fn             *make_request_fn;

             prep_rq_fn                *prep_rq_fn;

             unprep_rq_fn            *unprep_rq_fn;

             merge_bvec_fn                 *merge_bvec_fn;

             softirq_done_fn                 *softirq_done_fn;

             rq_timed_out_fn               *rq_timed_out_fn;

             dma_drain_needed_fn    *dma_drain_needed;

             lld_busy_fn                *lld_busy_fn;

     

             struct blk_mq_ops  *mq_ops;

     

             unsigned int              *mq_map;

     

             /* sw queues */

             struct blk_mq_ctx __percpu   *queue_ctx;

             unsigned int              nr_queues;

             struct blk_mq_hw_ctx     **queue_hw_ctx;

             unsigned int              nr_hw_queues;

             sector_t            end_sector;

             struct request          *boundary_rq;

             struct delayed_work        delay_work;

     

             struct backing_dev_info  backing_dev_info;

             void                    *queuedata;

             unsigned long           queue_flags;

             int                       id;

             gfp_t                           bounce_gfp;

                       __queue_lock;

             spinlock_t                  *queue_lock;

             struct kobject kobj;

             struct kobject mq_kobj;

             unsigned long           nr_requests;    /* Max # of requests */

             unsigned int              nr_congestion_on;

             unsigned int              nr_congestion_off;

             unsigned int              nr_batching;

     

             unsigned int              dma_drain_size;

             void                    *dma_drain_buffer;

             unsigned int              dma_pad_mask;

             unsigned int              dma_alignment;

     

             struct blk_queue_tag      *queue_tags;

             struct list_head        tag_busy_list;

     

             unsigned int              nr_sorted;

             unsigned int              in_flight[2];

             unsigned int              request_fn_active;

     

             unsigned int              rq_timeout;

             struct timer_list       timeout;

             struct list_head        timeout_list;

             struct list_head        icq_list;

             struct queue_limits limits;

             unsigned int              sg_timeout;

             unsigned int              sg_reserved_size;

             int                       node;

             unsigned int              flush_flags;

             unsigned int              flush_not_queueable:1;

             struct blk_flush_queue    *fq;

     

             struct list_head        requeue_list;

             spinlock_t                  requeue_lock;

             struct work_struct  requeue_work;

     

             struct mutex             sysfs_lock;

     

             int                       bypass_depth;

             int                       mq_freeze_depth;

     

             struct rcu_head                 rcu_head;

             wait_queue_head_t         mq_freeze_wq;

             struct percpu_ref    mq_usage_counter;

             struct list_head        all_q_node;

     

             struct blk_mq_tag_set    *tag_set;

             struct list_head        tag_set_list;

    };

    这里的第一个元素是queue_head,是linux内核特殊的list定义方式,这种定义法可以把不同的结构体串成一个list,这里的list的第一个元素就是request_queue,后续的都是request。也就是说后面来的新的request都是添加到这个队列中的。

     

    Queue属性

    Queue的标志

    #define QUEUE_FLAG_QUEUED      1       /*uses generic tag queueing */

    #define QUEUE_FLAG_STOPPED     2       /*queue is stopped */

    #define     QUEUE_FLAG_SYNCFULL         3       /*read queue has been filled */

    #define QUEUE_FLAG_ASYNCFULL 4       /*write queue has been filled */

    #define QUEUE_FLAG_DYING 5       /*queue being torn down */

    #define QUEUE_FLAG_BYPASS         6       /*act as dumb FIFO queue */

    #define QUEUE_FLAG_BIDI              7       /*queue supports bidi requests */

     

    QUEUE_FLAG_NOMERGES:直接不允许对队列的request进行merge操作

     

    #define QUEUE_FLAG_SAME_COMP      9       /*complete on same CPU-group */

    #define QUEUE_FLAG_FAIL_IO     10 /*fake timeout */

    #define QUEUE_FLAG_STACKABLE   11        /*supports request stacking */

    #define QUEUE_FLAG_NONROT      12     /*non-rotational device (SSD) */

    #define QUEUE_FLAG_VIRT        QUEUE_FLAG_NONROT /* paravirt device */

    #define QUEUE_FLAG_IO_STAT     13         /*do IO stats */

    #define QUEUE_FLAG_DISCARD     14       /*supports DISCARD */

    #define QUEUE_FLAG_NOXMERGES   15     /*No extended merges */

    #define QUEUE_FLAG_ADD_RANDOM  16  /*Contributes to random pool */

    #define QUEUE_FLAG_SECDISCARD  17       /*supports SECDISCARD */

    #define QUEUE_FLAG_SAME_FORCE  18      /*force complete on same CPU */

    #define QUEUE_FLAG_DEAD        19       /*queue tear-down finished */

    #define QUEUE_FLAG_INIT_DONE   20        /*queue is initialized */

    #define QUEUE_FLAG_NO_SG_MERGE 21     /* don't attempt to merge SG segments*/

    #define QUEUE_FLAG_SG_GAPS     22       /*queue doesn't support SG gaps */

     

    #define QUEUE_FLAG_DEFAULT      ((1 << QUEUE_FLAG_IO_STAT) |               \

                                          (1 << QUEUE_FLAG_STACKABLE)  |       \

                                          (1 << QUEUE_FLAG_SAME_COMP)       |       \

                                          (1 << QUEUE_FLAG_ADD_RANDOM))

     

    #define QUEUE_FLAG_MQ_DEFAULT      ((1 << QUEUE_FLAG_IO_STAT) |               \

                                          (1 << QUEUE_FLAG_SAME_COMP))

    queue的极限

     

    struct queue_limits {

             unsigned long           bounce_pfn;

             unsigned long           seg_boundary_mask;

             unsigned int              max_hw_sectors;

             unsigned int              chunk_sectors;

             unsigned int              max_sectors;

             unsigned int              max_segment_size;

             unsigned int              physical_block_size;

             unsigned int              alignment_offset;

             unsigned int              io_min;

             unsigned int              io_opt;

             unsigned int              max_discard_sectors;

             unsigned int              max_write_same_sectors;

             unsigned int              discard_granularity;

             unsigned int              discard_alignment;

     

             unsigned short                   logical_block_size;

             unsigned short                   max_segments;  //本队列最多可放的物理segment数,在合并操作前要检查合并前队列的总物理段数+合并的物理段数是否超过这个数

             unsigned short                   max_integrity_segments;

     

             unsigned char           misaligned;

             unsigned char           discard_misaligned;

             unsigned char           cluster;

             unsigned char           discard_zeroes_data;

             unsigned char           raid_partial_stripes_expensive;

    };

     

    电梯算法

             要实现电梯算法,需要知道电梯相关的元素:

    l  每个电梯算法的具体函数作为一个函数表要定义struct elevator_type结构体

    l  每个电梯算法都要有自己的队列组织(可以有多个队列),struct elevator_queue

    核心的元素是以上两个。定义好了以上两个结构,使用elv_register注册elevator_type,将request_queue的elevator域赋值为定义的elevator_queue即可。如此,系统在处理request_queue调用电梯算法的时候就可以找到算法的数据和函数了。

    要了解电梯算法的工作原理,具体的算法可以先略过,找到其框架流程更重要。这个流程函数是blk_queue_bio (struct request_queue *q, struct bio *bio)。一个参数是要插入的request队列,一个参数是传递下来的bio数据。

    当然在这个函数之上,作为整个通用块层的提交请求的入口函数是void submit_bio(int rw, struct bio *bio)。

    而submit_bio本质上是做一些统计记录之后就调用generic_make_request。generic_make_request的返回值不是使用函数返回值,而是使用bio本身提供的回调函数bio->bi_end_io。

    generic_make_request

             这个函数的流程是:

    l  检查bio

    n  检查长度是否超过设备的最大sector

    n  检查长度是否超出设备的队列长度

    n  检查bio是基于分区的还是基于设备的,如果是基于分区的,改为基于设备的

    u  再次检查是否超过设备的最大sector

    n  检查处理bio的rw域的各种可能取值

    n  尝试创建io_context(允许失败)

    n  调用throtle接口看是否需要对bio进行限制,需要的话进行限制

    l  将bio添加到设备的队列。如果设备队列当前为空,则直接处理该bio,而处理的时候如果发现队列又不为空了(即在处理的过程中有新的bio请求添加),则递归处理队列。

    blk_queue_bio

             实际的处理函数是blk_queue_bio。这个函数以设备的request_queue和要插入的bio作为参数,并且执行电梯算法。

    l  执行bounce操作,就是在开启了bounce情况下,将上层提交来的bio拷贝一份再向下传递(可以支持重传),是否开启bounce,取决于宏CONFIG_BOUNCE

    l  检查完整性测试是否可以通过。是否开启该功能取决于宏CONFIG_BLK_DEV_INTEGRITY

    l  如果队列允许合并

    n  调用blk_attempt_plug_merge。这个函数不是针对全部的request进行搜索合并,而是只针对要插入的bio搜索看有没有可以合并的的request,有的话只将该bio与该request合并。

    l  如果队列不允许合并

    n  执行电梯算法,执行前要锁定request_queue

     

    由于两种路径都要进行合并,一种是添加的时候查找合并,另一种是电梯合并,而在电梯合并的时候要对队列进行锁定。而老版本的内核只有电梯合并一种路径。接下来将重点讨论电梯合并的情况:

            

    el_ret = elv_merge(q, &req, bio);

             if (el_ret == ELEVATOR_BACK_MERGE) {

                       if (bio_attempt_back_merge(q, req, bio)) {

                                elv_bio_merged(q, req, bio);

                                if (!attempt_back_merge(q, req))

                                         elv_merged_request(q, req, el_ret);

                                goto out_unlock;

                       }

             } else if (el_ret == ELEVATOR_FRONT_MERGE) {

                       if (bio_attempt_front_merge(q, req, bio)) {

                                elv_bio_merged(q, req, bio);

                                if (!attempt_front_merge(q, req))

                                         elv_merged_request(q, req, el_ret);

                                goto out_unlock;

                       }

             }

             由于前置合并和后置合并类似,区别是后置合并要栋req->biotail,而前置合并只需要动bio,在动的方式又是一样的。所以这里只分析后置合并。

             值得注意的是,这里进入电梯算法是在发现可以合并的情况下,如果不可以合并(前后都不可以),程序会继续向下执行。(代码为简化版)

    req = get_request(q, rw_flags, bio, GFP_NOIO); //获得一个空闲的request结构体

    init_request_from_bio(req, bio);             //用bio初始化这个结构体

             plug = current->plug;

             if (plug) {                         //如果现在队列处于plug状态,简单的添加

                       if (!request_count)

                                trace_block_plug(q);

                       else {

                                if (request_count >= BLK_MAX_REQUEST_COUNT) {

                                         blk_flush_plug_list(plug, false);

                                         trace_block_plug(q);

                                }

                       }

                       list_add_tail(&req->queuelist, &plug->list);

                       blk_account_io_start(req, true);

             } else {                          //如果不是plug状态,就立即执行

                       spin_lock_irq(q->queue_lock);

                       add_acct_request(q, req, where);   //把request添加到队列q

                       __blk_run_queue(q);     //启动队列的执行

    out_unlock:

                       spin_unlock_irq(q->queue_lock);

             }

             add_acct_request(q,req, where)这个函数会调用电梯算法的elevator_add_req_fn,将request添加到电梯的队列。

    elv_merge (struct request_queue *q,struct request **req, struct bio *bio)

             这是电梯算法要执行的第一个函数。其首先尝试和queue->last_merge进行合并计算。如果不成功就hash搜索request_queue进行合并尝试。仍旧搜索不到才调用电梯算法计算。但是,这里很重要的是,这一步仅仅进行合并计算,也就是验证是否能够合并,具体的合并操作在blk_queue_bio函数中会根据elv_merge的返回值调用。

             传入的3个参数分别是request队列,作为返回值的标示可以合并的request的,和传入的bio。也就是说如果在q中找到了可以合并bio的request,就将该request通过req传出。

             这个函数的最后会调用电梯函数的elevator_merge_fn函数,看看电梯算法有没有合并的建议。电梯算法也只是计算看能不能按照电梯算法的需求合并,并不真正的进行合并。

    可合并路径

    bio_attempt_back_merge(structrequest_queue *q, struct request *req, struct bio *bio)

             传入的参数是队列q,队列中要合并的req和要合并的bio。

    l  由于每个request都有能携带的最大sector数。先判断如果合并是否会超出,会的话就返回,拒绝合并

    l  计算更新bio中的域:bi_phys_segments。

    l  计算bio的完整性检查是否通过(如果需要)

    l  判断bio可以合并进req,执行req->nr_phys_segments+= bio-> bi_phys_segments;

    l  进行IO数统计

    elv_bio_merged (struct request_queue *q,struct request *rq,struct bio *bio)

             此函数实际是调用电梯算法的elevator_bio_merged_fn函数。具体的内容执行与具体的电梯算法相关。电梯算法的分析稍后会进入。

             我们可以看出,虽然之前有合并的数值计算,但是此处才是真正的合并方法。

    attempt_back_merge (struct request_queue*q, struct request *rq)

    首先调用电梯算法提供的elevator_latter_req_fn。由于此时rq是之前的bio要合并进入的request,这个函数的作用就是找到q中的下个request,然后将这两个req进行合并。这里的怎么找是电梯算法的具体规定。

    但是合并之前可以做很多的检查,例如,现在是back_merge,就需要检查下个request的物理地址是否刚好在rq之后。还需要检查两个req的方向是否一致,所作用的目标设备是否一致。两个bio是否是同一个(有可能发生重传,但是这种情况目的地址就可以过滤掉,其实并不是必须的)。这里的合并参数调用了elv_merge_requests(elevator_merge_req_fn),也是电梯算法的函数。

    可以合并就合并两个request的参数。例如sector数目,物理sector的数目等。然后执行真实的合并操作。最后再把已经执行完合并操作的request放入队列。

    elv_merged_request

             实际调用的是电梯算法的elevator_merged_fn函数。上一步理论上是已经完成了合并。这些看起来重复的步骤其实是给电梯算法提供更多的选择。但是这一步进入的条件是上一步返回0,也就是合并不成功。

             比如,如果elevator_latter_req_fn不返回有效的request,这个函数就可以调用,而不用通用的合并框架代码。通用代码的最大缺点是只合并一个next,如果想要一次合并多个,就可以在这里实现,但是这种情况确实很少,因为每个request进来都会调用这个函数,除非新的bio可以导致两个本来不可合并的request相邻,否则一次的合并确实够用。

             这里的进入条件并不是说上次attempt_back_merge合并失败才会进入,而是attempt_back_merge发现需要合并并且已经完成了自己的动作,才会进入这里。也就是说进入这里就意味着合并必须要进行了,这里只是在合并需要进行的条件下通知电梯算法,让其做出适当的内部调整。

    不可合并路径

    __elv_add_request

             如果发现不可与已有的request合并,将实际的调用本函数。其插入位置有很多种:

    ELEVATOR_INSERT_SORT(默认) 、ELEVATOR_INSERT_FLUSH、ELEVATOR_INSERT_REQUEUE、ELEVATOR_INSERT_FRONT、ELEVATOR_INSERT_BACK、ELEVATOR_INSERT_SORT_MERGE、ELEVATOR_INSERT_SORT、ELEVATOR_INSERT_FLUSH。我们只看第一种,这是大部分bio走的路径。

             这一种首先将request的hash合并到电梯算法的哈希表,以让电梯算法可以见到这个请求的存在,然后调用电梯算法的q->elevator->type->ops.elevator_add_req_fn(q, rq); 进行实际的添加。

    总结

             由上文可以看到各个电梯函数在不同的时刻被调用,并且调用时很多电梯函数可以存在也可以不存在。

     

    struct elevator_ops

    {

             elevator_merge_fn *elevator_merge_fn;

             elevator_merged_fn *elevator_merged_fn;

             elevator_merge_req_fn *elevator_merge_req_fn;

             elevator_allow_merge_fn *elevator_allow_merge_fn;

             elevator_bio_merged_fn *elevator_bio_merged_fn;

     

             elevator_dispatch_fn *elevator_dispatch_fn;

             elevator_add_req_fn *elevator_add_req_fn;

             elevator_activate_req_fn *elevator_activate_req_fn;

             elevator_deactivate_req_fn *elevator_deactivate_req_fn;

     

             elevator_completed_req_fn *elevator_completed_req_fn;

     

             elevator_request_list_fn *elevator_former_req_fn;

             elevator_request_list_fn *elevator_latter_req_fn;

     

             elevator_init_icq_fn *elevator_init_icq_fn;    /* see iocontext.h */

             elevator_exit_icq_fn *elevator_exit_icq_fn;  /* ditto */

     

             elevator_set_req_fn *elevator_set_req_fn;

             elevator_put_req_fn *elevator_put_req_fn;

     

             elevator_may_queue_fn *elevator_may_queue_fn;

     

             elevator_init_fn *elevator_init_fn;

             elevator_exit_fn *elevator_exit_fn;

    };

             与判断是否可以合并相关的是elevator_merge_fn、elevator_merged_fn、 elevator_merge_req_fn三个函数。elevator_merge_fn用于判断是否可以合并,是向前合并还是向后合并,elevator_merged_fn是实际的更新request进行合并,如果是实际进行了合并操作,就会继续调用elevator_merged_fn,elevator_merged_fn是在确定了向前合并还是向后合并后调用的回调用来做本电梯算法内部数据的一些调整(根据是向前还是向后)

    plug机制

             如果当前的queue正在执行电梯算法,该queue就会处于plug状态。处于该状态的queue不会被真正的发送出去。这也是电梯算法的意义,电梯算法在执行时队列是要被锁定的,自然队列中的request也不能交给下层处理。执行完毕电梯算法后会unplug,队列流水线才可以正常执行。

    结构体

    struct elevator_queue

    {

             structelevator_type *type;

             void*elevator_data;

             structkobject kobj;

             structmutex sysfs_lock;

             unsignedint registered:1;

             DECLARE_HASHTABLE(hash,ELV_HASH_BITS);

    };

             每个电梯算法都有的队列。其中elevator_data存放电梯算法私有的数据,elevator_type存放电梯算法提供的操作。由于每个queue对应一个电梯算法,每个电梯算法对应一个elevator_queue结构体,所以这个结构体的存在就是为了电梯算法服务的。

             最后定义了哈希表。这个哈希表是排序过的,以request计算出key,添加的部分是request->hash域。也就是说每个新来加入队列的request请求,其hash域都会被在这里添加。

             当电梯算法执行时,电梯算法只需要考虑这个结构体。当添加一个新的request时,会将其首先添加到最后定义的hash标中,然后会调用电梯的elevator_add_req_fn,怎么样组织这些request取决于电梯算法的实现,但是都是组织在elevator_data中。这个结构每个电梯算法都可以自由定义其用途。

             也就是说这里的request会被添加两次。hash的那次用于日后的方便检索,而elevator_data的那次用于服务于电梯算法。在电梯算法运行处理时,其处理的对象就是elevator_data中由自己存放的数据。

    NOOP

    这部分是性能优化的关键。我们看一个最简单的noop方式。

     

    static struct elevator_type elevator_noop = {

             .ops = {

                       .elevator_merge_req_fn          = noop_merged_requests,

                       .elevator_dispatch_fn               = noop_dispatch,

                       .elevator_add_req_fn               = noop_add_request,

                       .elevator_former_req_fn                  = noop_former_request,

                       .elevator_latter_req_fn           = noop_latter_request,

                       .elevator_init_fn               = noop_init_queue,

                       .elevator_exit_fn              = noop_exit_queue,

             },

             .elevator_name = "noop",

             .elevator_owner = THIS_MODULE,

    };

     

    static int __init noop_init(void)

    {

             return elv_register(&elevator_noop);

    }

     

    static void __exit noop_exit(void)

    {

             elv_unregister(&elevator_noop);

    }

    可以看出使用方法。一个结构体,然后启动时注册,关闭时解注册即可。

    电梯算法有很多操作,这个noop定义的只是一部分。但是也是精简必须的。所以,我们考虑这种算法。

     

    noop_init_queue

    noop_init_queue函数定义这种算法如何安排它的request queue队列。内容就是生成elevator_queue结构体,并注册。

    struct noop_data是noop算法挂载在电梯结构体上的私有数据,挂载在elevator_data,这个数据仅仅是个list。

    struct noop_data{

             struct list_head queue;

    };

    noop_add_request

             这一步非常简单,仅仅是将request添加到电梯算法的队列elevator_data(noop_data)中。

    noop_latter_request、noop_former_request

             上文讲到,这个函数对应的电梯函数发生在bio合并进了request之后,寻找下一个可以跟已经合并的request进行合并的request。前后类似。这步发生的条件是bio可合并且已合并到已有的request。

             其返回的next简单的是所请求的request的next。

    noop_dispatch

             这一步是把noop_data的第一个元素取出来,重新排序加入request_queue队列。排序的方法是sector的顺序。这是处理队列,在IO调度算法的执行结束后,需要实际的执行request。调度算法执行的时候该request不在电梯主程序的控制范围,但是调度算法执行结束该request就通过本函数归还主程序的request_queue队列。

    noop_merged_requests

             这一步是直接把next_request从上层的request_queue中删除。

    DEADLINE

    static struct elevator_type iosched_deadline = {

             .ops = {

                       .elevator_merge_fn =              deadline_merge,

                       .elevator_merged_fn =             deadline_merged_request,

                       .elevator_merge_req_fn =      deadline_merged_requests,

                       .elevator_dispatch_fn =           deadline_dispatch_requests,

                       .elevator_add_req_fn =            deadline_add_request,

                       .elevator_former_req_fn =      elv_rb_former_request,

                       .elevator_latter_req_fn =        elv_rb_latter_request,

                       .elevator_init_fn =            deadline_init_queue,

                       .elevator_exit_fn =           deadline_exit_queue,

             },

     

             .elevator_attrs = deadline_attrs,

             .elevator_name = "deadline",

             .elevator_owner = THIS_MODULE,

    };

             这种算法也是比较简单的。算法的核心思想是request的sector临近的合并,并且保证不临近的都有一个适当的延时不至于饥饿,是标准的电梯算法。因为磁头移动的距离越短效率越高,但是总是如此移动就可能给远距离的请求带来饥饿。所以既要近距离移动磁头,又要保证远距离的请求不饥饿。要实现这个算法就需要两个结构体,一个rb_tree,一个fifo。rb_tree用来查找seoctor最靠近的request进行合并,而fifo用来拿到该要超时处理的接近饥饿的request。rb_tree中的节点是用request->__sector组织的。

             所以,在添加操作时(deadline_add_request)会同时添加到rb_tree和fifo。在处理时也要根据超时检查也要兼顾处理两个结构。而在合并操作时则大部分是使用rb_tree。

    展开全文
  • 刘正元: Linux 通用块层之IO合并

    千次阅读 2018-06-05 08:10:00
    刘正元: Linux 通用块层之DeadLine IO调度器 所谓请求合并就是将进程内或者进程间产生的在物理地址上连续的多个 IO 请求合并成单个 IO 请求一并处理,从而提升 IO 请求的处理效率。在前面有关通用块层介绍的系列文章...

    作者简介: 刘正元,来自天津麒麟(kylinos.cn), linux内核爱好者,对内核IO子系统和内核调试工具这块比较感兴趣,向内核上游内核贡献过一些,目前在公司负责文件IO协议栈的调试调优。

    相关阅读:

    宋宝华: 文件读写(BIO)波澜壮阔的一生

    刘正元: Linux 通用块层之DeadLine IO调度器

    所谓请求合并就是将进程内或者进程间产生的在物理地址上连续的多个IO请求合并成单个IO请求一并处理,从而提升IO请求的处理效率。在前面有关通用块层介绍的系列文章当中我们或多或少地提及了IO请求合并的概念,本篇我们从头集中梳理IO请求在block layer的来龙去脉,以此来增强对IO请求合并的理解。 
    首先来看一张图,下面的图展示了IO请求数据由用户进程产生,到最终持久化存储到物理存储介质,其间在内核空间所经历的数据流以及IO请求合并可能的触发点。


    从内核的角度而言,进程产生的IO路径主要有图中①②③所示的三条:

    ① 缓存IO, 对应图中的路径,系统中绝大部分IO走的这种形式,充分利用filesystem 层的page cache所带来的优势, 应用程序产生的IO经系统调用落入page cache之后便可以直接返回,page cache中的缓存数据由内核回写线程在适当时机负责同步到底层的存储介质之上,当然应用程序也可以主动发起回写过程(如fsync系统调用)来确保数据尽快同步到存储介质上,从而避免系统崩溃或者掉电带来的数据不一致性。缓存IO可以带来很多好处,首先应用程序将IO丢给page cache之后就直接返回了,避免了每次IO都将整个IO协议栈走一遍,从而减少了IO的延迟。其次,page cache中的缓存最后以页或块为单位进行回写,并非应用程序向page cache中提交了几次IO, 回写的时候就需要往通用块层提交几次IO, 这样在提交时间上不连续但在空间上连续的小块IO请求就可以合并到同一个缓存页中一并处理。再次,如果应用程序之前产生的IO已经在page cache中,后续又产生了相同的IO,那么只需要将后到的IO覆盖page cache中的旧IO,这样一来如果应用程序频繁的操作文件的同一个位置,我们只需要向底层存储设备提交最后一次IO就可以了。最后,应用程序写入到page cache中的缓存数据可以为后续的读操作服务,读取数据的时候先搜索page cache,如果命中了则直接返回,如果没命中则从底层读取并保存到page cache中,下次再读的时候便可以从page cache中命中。

    ② 非缓存IO(带蓄流),对应图中的路径,这种IO绕过文件系统层的cache。用户在打开要读写的文件的时候需要加上“O_DIRECT”标志,意为直接IO,不让文件系统的page cache介入。从用户角度而言,应用程序能直接控制的IO形式除了上面提到的缓存IO”,剩下的IO都走的这种形式,就算文件打开时加上了 ”O_SYNC” 标志,最终产生的IO也会进入蓄流链表(图中的Plug List)。如果应用程序在用户空间自己做了缓存,那么就可以使用这种IO方式,常见的如数据库应用。

    ③ 非缓存IO(不带蓄流),对应图中的路径,内核通用块层的蓄流机制只给内核空间提供了接口来控制IO请求是否蓄流,用户空间进程没有办法控制提交的IO请求进入通用块层的时候是否蓄流。严格的说用户空间直接产生的IO都会走蓄流路径,哪怕是IO的时候附上了“O_DIRECT” ”O_SYNC”标志(可以参考《Linux通用块层介绍(part1: bio层)》中的蓄流章节),用户间接产生的IO,如文件系统日志数据、元数据,有的不会走蓄流路径而是直接进入调度队列尽快得到调度。注意一点,通用块层的蓄流只提供机制和接口而不提供策略,至于需不需要蓄流、何时蓄流完全由内核中的IO派发者决定。

    应用程序不管使用图中哪条IO路径,内核都会想方设法对IO进行合并。内核为促进这种合并,在IO协议栈上设置了三个最佳狙击点:

    Cache (页高速缓存)

    Plug List (蓄流链表)

    Elevator Queue (调度队列)

    cache 合并

    IO处在文件系统层的page cache中时只有IO数据,还没有IO请求(bio request,只有page cache 在读写的时候才会产生IO请求。本文主要介绍IO请求在通用块层的合并,因此对于IO cache 层的合并只做现象分析,不深入到内部逻辑和代码细节。 
    如果是缓存IO,用户进程提交的写数据会积聚在page cache 中。cache 保存IO数据的基本单位为page,大小一般为4K, 因此cache 又叫页高速缓存, 用户进程提交的小块数据可以缓存到cache中的同一个page中,最后回写线程将一个page中的数据一次性提交给通用块层处理。以dd程序写一个裸设备为例,每次写1K数据,连续写16次:

    dd if=/dev/zero of=/dev/sdb bs=1k count=16

    通过blktrace观测的结果为: 

    blktrace -d /dev/sdb -o - | blkparse -i -

    bio请求在通用块层的处理情况主要是通过第六列反映出来的如果对blkparse的输出不太了解,可以 man 一下blktrace。对照每一行的输出来看看应用程序产生的写IO经由page cache之后是如何派发到通用块层的:

    现阶段只关注IO是如何从page cache中派发到通用块层的,所以后面的泻流、派发过程没有贴出来。回写线程–kworker8个扇区(扇区大小为512B, 8个扇区为4K对应一个page大小)为单位将dd程序读写的1K数据块派发给通用块层处理。dd程序写了16次,回写线程只写了4次(对应四次Q),page cache的缓存功能有效的合并了应用程序直接产生的IO数据。
    文件系统层的page cache对读IO也有一定的作用,带缓存的读IO会触发文件系统层的预读机制,所谓预读有专门的预读算法,通过判断用户进程IO趋势,提前将存储介质上的数据块读入page cache中,下次读操作来时可以直接从page cache中命中,而不需要每次都发起对块设备的读请求。还是以dd程序读一个裸设备为例,每次读1K数据,连续读16次:

    dd if=/dev/sdb of=/dev/zero bs=1K count=16

    通过blktrace观测的结果为:

    blktrace -d /dev/sdb -o - | blkparse -i -

    同样只关注IO是如何从上层派发到通用块层的,不关注IO在通用块层的具体情况,先不考虑PIUDC等操作,那么上面的输出可以简单解析为:

    读操作是同步的,所以触发读请求的是dd进程本身。dd进程发起了16次读操作,总共读取16K数据,但是预读机制只向底层发送了两次读请求,分别为0+32(16K), 32+64(32K),总共预读了16 + 32 = 48K数据,并保存到cache中,多预读的数据可以为后续的读操作服务。

    plug 合并

    在阅读本节之前可以先回顾下linuxer公众号中介绍biorequest的系列文章,熟悉IO请求在通用块层的处理,以及蓄流(plug)机制的原理和接口。特别推荐宋宝华老师写的《文件读写(BIO)波澜壮阔的一生》,通俗易懂地介绍了一个文件io的生命周期。

    每个进程都有一个私有的蓄流链表,进程在往通用块层派发IO之前如果开启了蓄流功能,那么IO请求在被发送给IO调度器之前都保存在蓄流链表中,直到泄流(unplug)的时候才批量交给调度器。蓄流的主要目的就是为了增加请求合并的机会,bio在进入蓄流链表之前会尝试与蓄流链表中保存的request进行合并,使用的接口为blk_attempt_plug_merge(). 本文是基于内核4.17分析的,源码来源于4.17-rc1

    代码遍历蓄流链表中的request,使用blk_try_merge找到一个能与bio合并的request并判断合并类型,蓄流链表中的合并类型有三种:ELEVATOR_BACK_MERGEELEVATOR_FRONT_MERGEELEVATOR_DISCARD_MERGE。普通文件IO操作只会进行前两种合并,第三种是丢弃操作的合并,不是普通的IO的合并,故不讨论。

    bio后向合并 (ELEVATOR_BACK_MERGE)

    为了验证IO请求在通用块层的各种合并形式,准备了以下测试程序,该测试程序使用内核原生支持的异步IO引擎,可异步地向内核一次提交多个IO请求。为了减少page cache和文件系统的干扰,使用O_DIRECT的方式直接向裸设备派发IO

    iotc.c

    ...

    /* dispatch 3 4k-size ios using the io_type specified by user */

    #define NUM_EVENTS  3

    #define ALIGN_SIZE  4096

    #define WR_SIZE  4096

    enum io_type {

    SEQUENCE_IO,/* dispatch 3 ios: 0-4k(0+8), 4-8k(8+8), 8-12k(16+8) */

    REVERSE_IO,/* dispatch 3 ios: 8-12k(16+8), 4-8k(8+8),0-4k(0+8) */

    INTERLEAVE_IO, /* dispatch 3 ios: 8-12k(16+8), 0-4k(0+8),4-8k(8+8) */ ,

    IO_TYPE_END

    };


    int io_units[IO_TYPE_END][NUM_EVENTS] = {

    {0, 1, 2}, /* corresponding to SEQUENCE_IO */

    {2, 1, 0}, /* corresponding to REVERSE_IO */

    {2, 0, 1} /* corresponding to INTERLEAVE_IO */

    };


    char *io_opt = "srid:"; /* acceptable options */


    int main(int argc, char *argv[])

    {

    int fd;

    io_context_t ctx;

    struct timespec tms;

    struct io_event events[NUM_EVENTS];

    struct iocb iocbs[NUM_EVENTS],

                    *iocbp[NUM_EVENTS];

    int i, io_flag = -1;;

    void *buf;

    bool hit = false;

    char *dev = NULL, opt;


    /* io_flag and dev got set according the options passed by user , don’t paste the code of parsing here to shrink space */

    fd = open(dev, O_RDWR | __O_DIRECT);


    /* we can dispatch 32 IOs at 1 systemcall */

    ctx = 0;


    io_setup(32, &ctx);

    posix_memalign(&buf,ALIGN_SIZE,WR_SIZE);


    /* prepare IO request according to io_type */

    for (i = 0; i < NUM_EVENTS; iocbp[i] = iocbs + i, ++i)

    io_prep_pwrite(&iocbs[i], fd, buf, WR_SIZE, io_units[io_flag][i] * WR_SIZE);


    /* submit IOs using io_submit systemcall */

    io_submit(ctx, NUM_EVENTS, iocbp);


    /* get the IO result with a timeout of 1S*/

    tms.tv_sec = 1;

    tms.tv_nsec = 0;

    io_getevents(ctx, 1, NUM_EVENTS, events, &tms);


    return 0;

    }

    测试程序接收两个参数,第一个为作用的设备,第二个为IO类型,定义了三种IO类型:SEQUENCE_IO(顺序),REVERSE_IO(逆序),INTERLEAVE_IO(交替)分别用来验证蓄流阶段的bio后向合并、前向合并和泄流阶段的request合并。为了减少篇幅,此处贴出的源码删除了选项解析和容错处理,只保留主干,原版位于:https://github.com/liuzhengyuan/iotc

    为验证bio在蓄流阶段的后向合并,用上面的测试程序iotc顺序派发三个写io:

    # ./iotc  -d  /dev/sdb  -s

    -d 指定作用的设备sdb-s 指定IO方式为SEQUENCE_IO(顺序),表示顺序发起三个写请求: bio0(0 + 8), bio1(8 + 8), bio2(16 + 8)。通过blktrace来观察iotc派发的bio请求在通用块层蓄流链表中的合并情况:

    blktrace -d /dev/sdb -o - | blkparse -i -

    上面的输出可以简单解析为:

    第一个bio(bio0)进入通用块层时,此时蓄流链表为空,于是申请一个request并用bio0初始化,再将request添加进蓄流链表,同时告诉blktrace蓄流已正式工作。第二个bio(bio1)到来的时候会走blk_attempt_plug_merge的逻辑,尝试调用bio_attempt_back_merge与蓄流链表中的request合并,发现正好能合并到第一个bio所在的request尾部,于是直接返回。第三个bio(bio2)的处理与第二个同理。通过蓄流合并之后,三个IO请求最终合并成了一个request(0 + 24)。用一副图来展示整个合并过程:

    bio前向合并 (ELEVATOR_FRONT_MERGE)

    为验证bio在蓄流阶段的前向合并,使用iotc逆序派发三个写io:

    # ./iotc  -d  /dev/sdb  -r

    -r 指定IO方式为REVERSE_IO(逆序),表示逆序发起三个写请求: bio0(16 + 8),bio1(8 + 8), bio2(0 + 8)blktrace的观察结果为:

    blktrace -d /dev/sdb -o - | blkparse -i -

    上面的输出可以简单解析为:

    与前面的后向合并相比,唯一的区别是合并方式由之前的”M”变成了现在的”F”,即在blk_attempt_plug_merge中走的是bio_attempt_front_merge分支。通过下面的图来展示前向合并过程:

    “plug 合并不会做requestrequest的进阶合并,蓄流链表中的request之间的合并会在泄流的时候做,即在下面介绍的“elevator 合并中做。

    elevator 合并

    上面讲到的蓄流链表合并是为进程内的IO请求服务的,每个进程只往自己的蓄流链表中提交IO请求,进程间的蓄流链表相互独立,互不干涉。但是,多个进程可以同时对一个设备发起IO请求,那么通用块层还需要提供一个节点,让进程间的IO请求有机会进行合并。一个块设备有且仅有一个请求队列(调度队列),所有对块设备的IO请求都需要经过这个公共节点,因此调度队列(Elevator Queue)是IO请求合并的另一个节点。 
    先回顾一下通用块层处理IO请求的核心函数:blk_queue_bio(), 上层派发的bio请求都会流经该函数,或将bio蓄流到Plug List,或将bio合并到Elevator Queue, 或将bio生成request直接插入到Elevator Queueblk_queue_bio()的主要处理流程为:

    其中”A”标识的合并到蓄流链表的request就是上一章介绍的“plug 合并bio如果不能合并到蓄流链表中接下来会尝试合并到“B”标识的合并到调度队列的request合并到调度队列的request只是“elevator 合并的第一个点。你可能已经发现了blk_queue_bio()bio合并到蓄流链表或者将request添加进蓄流链表之后就没管了,从路径可以发现蓄流链表中的request最终都是要交给电梯调度队列的,这正是”elevator 合并的第二个点,关于泄流的时机请参考我之前写的《Linux通用块层介绍(part1: bio层)》。下面分别介绍这两个合并点:

    bio合并到elevator

    先看B表示的代码段:

    blk_queue_bio:

            switch (elv_merge(q, &req, bio)) {

            case ELEVATOR_BACK_MERGE:

                    if (!bio_attempt_back_merge(q, req, bio))

                            break;

                    elv_bio_merged(q, req, bio);

                    free = attempt_back_merge(q, req);

                    if (free)

                            __blk_put_request(q, free);

                    else

                            elv_merged_request(q, req, ELEVATOR_BACK_MERGE);

                    goto out_unlock;

            case ELEVATOR_FRONT_MERGE:

                    if (!bio_attempt_front_merge(q, req, bio))

                            break;

                    elv_bio_merged(q, req, bio);

                    free = attempt_front_merge(q, req);

                    if (free)

                            __blk_put_request(q, free);

                    else

                            elv_merged_request(q, req, ELEVATOR_FRONT_MERGE);

                    goto out_unlock;

            default:

                    break;

            }


    合并逻辑基本与”plug 合并相似,先调用elv_merge接口判断合并类型,然后根据是后向合并或是前向合并分别调用bio_attempt_back_mergebio_attempt_front_merge进行合并操作,由于操作对象从蓄流链表变成了电梯调度队列,bio合并完了之后还需额外干几件事:

    1. 调用elv_bio_merged, 该函数会调用电梯调度器注册的elevator_bio_merged_fn接口来通知调度器做相应的处理,对于deadline调度器而言该接口为NULL

    2.寻找进阶合并,参考我之前写的《Linux通用块层介绍(part2: request层)》中对进阶合并的描述,如果bio产生了后向合并,则调用attempt_back_merge试图进行后向进阶合并,如果bio产生了前向合并,则调用attempt_front_merge企图进行前向进阶合并。deadline的进阶合并接口为deadline_merged_requests, 被合并的request会从调度队列中删除。通过下面的图示来展示后向进阶合并过程,前向进阶合并同理。

        3. 如果产生了进阶合并,则被合并的request可以释放了,参考上图,可调用blk_put_request进行回收。如果只产生了bio合并,合并后的request的长度和扇区地址都会发生变化,需要调用elv_merged_request->elevator_merged_fn来更新合并后的请求在调度队列的位置。deadline对应的接口为deadline_merged_request,其相应的操作为将合并的request先从调度队列移出再重新插进去。

    “bio合并到elevator”的合并形式只会发生在进程间,即只有一个进程在IO的时候不会产生这种合并形式,原因在于进程在向调度队列派发IO请求或者试图与将bio与调度队列中的请求合并的时候是持有设备的队列锁得,其他进程是不能往调度队列派发请求,这也是通用块层单队列通道窄需要发展多队列的主要原因之一,只有进程在将调度队列中的request逐个派发给驱动层的时候才会将设备队列锁重新打开,即只有当一个进程在将调度队列中request派发给驱动的时候其他进程才有机会将bio合并到还未派发完的request中。所以想通过简单的IO测试程序来捕捉这种形式的合并比较困难,这对两个IO进程的IO产生时序有非常高的要求,故不演示。有兴趣的可以参考上面的github仓库,里面有patch对内核特定的请求派发位置加上延时来改变IO请求本来的时序,从而让测试程序人为的达到这种碰撞效果。

    request在泄流的时候合并到elevator

    通用块层的泄流接口为:blk_flush_plug_list(), 该接口主要的处理逻辑如下图所示

    其中请求合并发生的点在__elv_add_request()blk_flush_plug_list会遍历蓄流链表中的每个request,然后将每个request通过 _elv_add_request接口添加到调度队列中,添加的过程中会尝试与调度队列中已有的request进行合并。

    __elv_add_request:

            case ELEVATOR_INSERT_SORT_MERGE:

                    /*

                     * If we succeed in merging this request with one in the

                     * queue already, we are done - rq has now been freed,

                     * so no need to do anything further.

                     */

                    if (elv_attempt_insert_merge(q, rq))

                            break;

                    /* fall through */

            case ELEVATOR_INSERT_SORT:

                    BUG_ON(blk_rq_is_passthrough(rq));

                    rq->rq_flags |= RQF_SORTED;

                    q->nr_sorted++;

                    if (rq_mergeable(rq)) {

                            elv_rqhash_add(q, rq);

                            if (!q->last_merge)

                                    q->last_merge = rq;

                    }

                    q->elevator->type->ops.sq.elevator_add_req_fn(q, rq);

                    break;


    泄流时走的是ELEVATOR_INSERT_SORT_MERGE分支,正如注释所说的先让蓄流的request调用elv_attempt_insert_merge尝试与调度队列中的request合并,如果不能合并则落入到ELEVATOR_INSERT_SORT分支,该分支直接调用电梯调度器注册的elevator_add_req_fn接口将新来的request插入到调度队列合适的位置。其中elv_rqhash_add是将新加入到调度队列的requesthash索引,这样做的好处是加快从调度队列寻找可合并的request的索引速度。 
    在泄流的时候调度队列中既有其他进程产生的request,也有当前进程从蓄流链表中派发的requestblk_flush_plug_list是先将所有request派发到调度队列再一次性queue_unplugged,而不是派发一个requestqueue_unplugged)。所以“request在泄流的时候合并到elevator”既是进程内的,也可以是进程间的。 
    elv_attempt_insert_merge的实现只做request间的后向合并,即只会将一个request合并到调度队列中的request的尾部。这对于单进程IO而言足够了,因为blk_flush_plug_list在泄流的时候已经将蓄流链表中的request进行了list_sort(按扇区排序)。笔者曾经提交过促进进程间request的前向合并的patch(见github),但没被接收,maintainer–Jens的解析是这种IO场景很难发生,如果产生这种IO场景基本是应用程序设计不合理。通过增加时间和空间来优化一个并不常见的场景并不可取。 
    最后通过一个例子来验证进程内“request在泄流的时候合并到elevator”,进程间的合并同样对请求派发时序有很强的要求,在此不演示,github中有相应的测试patch和测试方法。iotc使用下面的方式派发三个写io:

    # ./iotc  -d  /dev/sdb  -i

    -i指定IO方式为INTERLEAVE_IO(交替),表示按扇区交替的方式发起三个写请求: bio0(16 + 8),bio1(8 + 8), bio2(0 + 8)blktrace的观察结果为:

    blktrace -d /dev/sdb -o - | blkparse -i -

    上面的输出可以简单解析为:

    bio0(16 + 8)先到达plug listbio1(0+8)到达时发现不能与plug list中的request合并,于是申请一个request添加到plug listbio2(8+8)到达时首先与bio1进行后向合并。之后进程触发泄流,泄流接口函数会将plug list中的request排序,因此request(0+16)先派发到调度队列,此时调度队列为空不能进行合并。然后派发request(16+8),派发时调用elv_attempt_insert_merge接口尝试与调度队列中的其他request进行合并,发现可以与request(0+16)进行后向合并,于是两个request合并成一个,最后向设备驱动派发的只有一个request(0+24)。整个过程可以用下面的图来展示:

    小结

    通过cache plugelevator自上而下的三层狙击,应用程序产生的IO能最大限度的进行合并,从而提升IO带宽,降低IO延迟,延长设备寿命。page cache打头阵,既做数据缓存又做IO合并,主要是针对小块IO进行合并,因为使用内存页做缓存,所以合并后的最大IO单元为页大小,当然对于大块IO,page cache也会将它拆分成以页为单位下发,这不影响最终的效果,因为后面还有plug elevator补刀。plug list竭尽全力合并进程内产生的IO, 从设备的角度而言进程内产生的IO相关性更强,合并的可能性更大,plug list设计位于elevator queue之上而且又是每个进程私有的,因此plug list既有利于IO合并,又减轻了elevator queue的负担。elevator queue更多的是承担进程间IO的合并,用来弥补plug list对进程间合并的不足,如果是带缓存的IO,这种IO合并基本上不会出现。从实际应用角度出发,IO合并更多的是发生在page cacheplug list中。

    (完)

    "Linux阅码场"是专业的Linux及系统软件技术交流社区,Linux系统人才培养基地,企业和Linux人才的连接枢纽。


    查看我们精华技术文章请移步:

    Linuxer精华文章汇总


    求职招聘请移步:

    Linuxer: 连接企业和Linux人才的platform总线


    扫描二维码关注我们 

    如果觉得好,请

    转发

    转发

    转发

    展开全文
  • 通用块设备驱动程序框架分析

    千次阅读 2016-02-14 20:56:53
    设备和字符设备驱动在IO操作方面的区别还包括:(1)设备驱动程序特点是通常以(Sector)为单位的IO操作如Flash、磁盘等存储介质,而字符设备则大多数以字节为单位。(2)字符设备只能被顺序读定,而设备...

    1 引言

        驱动程序可发分为三大类型:字符设备驱动程序、块设备驱动程序和网络设备驱动程序。块设备和字符设备驱动在IO操作方面的区别还包括:(1)块设备驱动程序特点是通常以块(Sector)为单位的IO操作如Flash、磁盘等存储介质,而字符设备则大多数以字节为单位。(2)字符设备只能被顺序读定,而块设备可以随机访问。(3)块设备相对于IO请求有对应的缓冲区,而且缓冲区的数据到具体设备上并非实时的,(一个非常经典的例子是在安全删除U盘时,有时需要等待很长一段时间,这时间就是将缓冲区的数据刷新到实际设备上)。这样做的原因一是因为块设备的读写量较大,而且访问是随机的,所以如果不经过缓冲,然后优化读写,会降低读写效率。例如,在一秒内应用程序先后访问“磁盘1柱面0上的扇区1”、“磁盘0柱面0上的扇区3”和“磁盘1柱面0上的扇区2”,如果不进行优化,那么显然磁头需要来回跳转,效率不高,如果将操作3和操作2进行调整,可以显著提高效率。所以对于块设备的读写,需要设置缓冲区,进行优化。

    2 块设备驱动的结构层次


        如图所示,本文主要讲解通用的块设备驱动,不局限在各种存储子系统的细分下,换而言之,实现一个”XXX存储子系统”,提供和使用与块IO调度层和硬件层的接口实现方法。

        应用程序:即调用open(“1.txt”);

        虚拟文件系统:根据设备名称寻找到对应的驱动函数;它能够识别出,是字符设备文件、块设备文件还是普通文件,进而调用不同的处理函数。

        文件系统:将对文件的读写转换成对硬件设备扇区的读写;

        块IO调度层:即实现各种调度算法的层次,主要实现的代码集中在ll_rw_block.c。主要功能是维护队列和提供优化缓存的算法。为下层具体的硬件存储子系统,提供队列接口函数。上层应用程序经过文件系统转换为对应扇区的读写操作请求,这些操作内核描述为一个bio,由上可知,经过调度算法后,不一定立即对硬件设备读写,而是将请求缓存,即而组成一个队列。所以队列是经过调度算法优化的读写操作请求集合。

        各种存储设备子系统层:即针对各种设备都有自己的框架,例如mtd的存储子系统,抽象出来了一套自己的框架,虽然也向上块IO调度层提供了队列处理函数,但实际读写硬件设备是在自己的队列处理函数实现。[Linux内核的开发维护者总是千方百计地提供一系列标准框架,简化硬件芯片驱动需要做的工作,个人感觉驱动开发其实并不是特别难的事,难的是制定框架的工作]

    3 主要接口

    3.1 int register_blkdev(unsignedint major, const char *name)

     

    3.2 request_queue_t * blk_init_queue(request_fn_proc *rfn, spinlock_t *lock)

        向“块IO调度层”提供队列的处理函数。注意以下几点

        (1)无论是何种硬件制定的子系统驱动框架,都需要向上层-块IO调度层(ll_rw_block.c)提供该处理函数。

        (2)该函数的调用并不能由驱动自己调用,只有当内核认为是时候让驱动处理对设备的读写操作时,它才调用这个函数。

        (3)该函数的主要工作就是发起与request对应的块设备IO动作(但是具体的IO工作不一定要在该函数内同步完成)例如mmc或者mtd子系统中的该函数实现都不是直接操作IO,而是唤醒操作IO的线程处理函数。

     

    3.3 struct gendisk *alloc_disk(int minors) 和voidadd_disk(struct gendisk *disk) 的gendisk处理函数

    Gendisk 通用结构体表示独立的磁盘设备(或分区),“3.2”中申请的队列也属于其成员。

     

    3.3 struct request *elv_next_request(request_queue_t *q)

    从队列中取出需要操作的队列

     

    3.4 void end_request(structrequest *req, int uptodate)

    当处理完一个队列后,需要提交,告知内核已经完成操作该队列。

     

    4 主要操作流程

    4.1 初始化部分

    (1)申请一个gendisk结构体,以及初始化一个读写队列(申请);

    (2)设置gendisk结构体还有其它属性(设置);

    (3)注册块设备以及gendisk(注册);

    4.2 读写队列处理函数

    (1)取出一个队列;

    (2)执行相应的读写操作;

    (3)报告完成;

    5 示例代码

        内存虚拟一块存储空间作为块设备。(来自其它博客,但已经验证过)。

     

    #include <linux/module.h>
    #include <linux/errno.h>
    #include <linux/interrupt.h>
    #include <linux/mm.h>
    #include <linux/fs.h>
    #include <linux/kernel.h>
    #include <linux/timer.h>
    #include <linux/genhd.h>
    #include <linux/hdreg.h>
    #include <linux/ioport.h>
    #include <linux/init.h>
    #include <linux/wait.h>
    #include <linux/blkdev.h>
    #include <linux/blkpg.h>
    #include <linux/delay.h>
    #include <linux/io.h>
    
    #include <asm/system.h>
    #include <asm/uaccess.h>
    #include <asm/dma.h>
    
    static struct gendisk *ramblock_disk;
    static request_queue_t *ramblock_queue;
    
    static int major;
    
    static DEFINE_SPINLOCK(ramblock_lock);
    
    #define RAMBLOCK_SIZE (1024*1024)
    static unsigned char *ramblock_buf;
    
    static int ramblock_getgeo(struct block_device *bdev, struct hd_geometry *geo)
    {
    	/* 容量=heads*cylinders*sectors*512 */
    	geo->heads     = 2;
    	geo->cylinders = 32;
    	geo->sectors   = RAMBLOCK_SIZE/2/32/512;
    	return 0;
    }
    
    
    static struct block_device_operations ramblock_fops = {
    	.owner	= THIS_MODULE,
    	.getgeo	= ramblock_getgeo,
    };
    
    static void do_ramblock_request(request_queue_t * q)
    {
    	static int r_cnt = 0;
    	static int w_cnt = 0;
    	struct request *req;
    	
    	//printk("do_ramblock_request %d\n", ++cnt);
    
      //1. 循环取出队列
    	while ((req = elv_next_request(q)) != NULL) {                 
    	//2. 操作队列
    		/* 数据传输三要素: 源,目的,长度 */
    		/* 源/目的: */
    		unsigned long offset = req->sector * 512;
    
    		/* 目的/源: */
    		// req->buffer
    
    		/* 长度: */		
    		unsigned long len = req->current_nr_sectors * 512;
    
    		if (rq_data_dir(req) == READ)
    		{
    			//printk("do_ramblock_request read %d\n", ++r_cnt);
    			memcpy(req->buffer, ramblock_buf+offset, len);
    		}
    		else
    		{
    			//printk("do_ramblock_request write %d\n", ++w_cnt);
    			memcpy(ramblock_buf+offset, req->buffer, len);
    		}		
    		//3 报告完成
    		end_request(req, 1);
    	}
    }
    
    static int ramblock_init(void)
    {
    	/* 1. 分配一个gendisk结构体 */
    	ramblock_disk = alloc_disk(16); /* 次设备号个数: 分区个数+1 */
    
    	/* 2. 设置 */
    	/* 2.1 分配/设置队列: 提供读写能力 */
    	ramblock_queue = blk_init_queue(do_ramblock_request, &ramblock_lock);
    	ramblock_disk->queue = ramblock_queue;
    	
    	/* 2.2 设置其他属性: 比如容量 */
    	major = register_blkdev(0, "ramblock");  /* cat /proc/devices */	
    	ramblock_disk->major       = major;
    	ramblock_disk->first_minor = 0;
    	sprintf(ramblock_disk->disk_name, "ramblock");
    	ramblock_disk->fops        = &ramblock_fops;
    	set_capacity(ramblock_disk, RAMBLOCK_SIZE / 512);
    
    	/* 3. 硬件相关操作 */
    	ramblock_buf = kzalloc(RAMBLOCK_SIZE, GFP_KERNEL);
    
    	/* 4. 注册 */
    	add_disk(ramblock_disk);
    
    	return 0;
    }
    
    static void ramblock_exit(void)
    {
    	unregister_blkdev(major, "ramblock");
    	del_gendisk(ramblock_disk);
    	put_disk(ramblock_disk);
    	blk_cleanup_queue(ramblock_queue);
    
    	kfree(ramblock_buf);
    }
    
    module_init(ramblock_init);
    module_exit(ramblock_exit);
    
    MODULE_LICENSE("GPL");
    

     

    参考文献:

    [1] 《Linux设备驱动开发详解》-宋宝华

     

    展开全文
  • 块层介绍 第一篇: bio层

    千次阅读 2018-03-25 00:00:00
    摘要: 本文翻译自Neil Brown发表在LWN上的两篇介绍块层的文章。Neil是前MD RAID的maintainer,他通过这两篇文章,提纲契领地描绘了块层的主脉络。操作系统比如Linux关键的价值之一,就是为具体的设备提供了抽象接口...
  • Java线程怎样映射到操作系统线程

    千次阅读 2019-04-06 22:07:31
    先说多线程模型,参考经典教材《Operating System Concepts , Silberschatz ,9th edition》 中文版是《操作系统概念,第9版》 https://www.cs.uic.edu/~jbell/CourseNotes/OperatingSystems/4_Threads.html 一...
  • 线程专题总结

    千次阅读 2012-08-08 14:24:36
    haoxue 2011-01-08 21:03 [iOS]深入浅出 iOS 之多线程 NSThread  ...iOS 支持多个层次的多线程...Thread 是这三种范式里面相对轻量级的,但也是使用起来最负责的,你需要自己管理thread的生命周期,线程之间的
  • windows 线程

    千次阅读 2016-09-14 00:06:14
    在windows中进程只是一个容器,用于装载系统资源,它并不执行代码,它是系统资源分配的最小单元,而在进程中执行代码的是线程线程是轻量级的进程,是代码执行的最小单位。 从系统的内核角度看,进程是一个内核...
  • 线程面试题总结

    千次阅读 多人点赞 2019-06-11 00:04:49
    线程面试题总结 什么是线程线程是操作系统能够进行运算调度的最小单位,它被包含在进程之中,是进程中的实际运作单位,可以使用多线程对进行运算提速。 比如,如果一个线程完成一个任务要100毫秒,那么用十个线程...
  • 最简单的改进即是使用多线程(或多进程)服务器模型,在应用级别,我们一般采用多线程模式。多线程能让多个客户端同时请求,并能几乎同时对这些请求进行响应,而不用排队一个一个处理,能同时为多个客户端提供一问...
  • 内核线程

    千次阅读 2012-12-31 14:06:07
    1 > 线程和进程的差别 线程机制支持并发程序设计技术,在多处理器上能真正保证并行处理。而在linux实现线程很特别,linux把所有的线程都当作线程实现。 linux下线程看起来就像普通进程(只是该进程和其他进程共享...
  • JAVA线程知识点

    千次阅读 2018-09-12 18:30:12
    java线程知识点大全 java线程知识点大全 1、 什么是线程? 1、 什么是线程线程是操作系统能够进行运算的最小单位,他包含在实际的运作单位里面,是进程中的实际运作单位。 程序员可以通过它进行...
  • 同步要领下面的表格列展了.NET对协调或同步线程动作的可用的工具:简易阻止方法构成目的Sleep阻止给定的时间周期Join等待另一个线程完成锁系统构成目的跨进程?速度lock确保只有一个线程访问某个资源或某段代码。否...
  • Java多线程和并发

    千次阅读 2019-10-22 13:46:54
    Java多线程和并发多进程多进程概念多进程优点多进程缺点多线程多进程和多线程对比Java多线程创建Java多线程启动多线程实现对比多线程信息共享线程类通过共享变量在多个线程中共享消息多线程信息共享问题变量副本问题...
  • <br />转自:http://info.52z.com/html/23863.html<br />线程数量)作者:多线程 来源:本站整理 发布时间:2008-9-24 8:52:43 同步要领 下面的表格列展了.NET对协调或同步线程动作的可用的工具: ...
  • 2 线程的经典模型通常来说经典的线程模型和普通的进程模型都是类似的只是在共享资源的问题上有所不同,这里已经放在了上一节中不再详细描述,这里讨论下线程的两种实现方式,这里也是我看书的时候比较难以理解的部分...
  • java多线程线程运行时的内存模型

    千次阅读 2018-03-29 16:20:30
    本文链接地址: Java内存模型 Java内存模型规范了Java虚拟机与计算机内存是如何协同工作的。Java虚拟机是一个完整的计算机的一个...Java内存模型规定了如何和何时可以看到由其他线程修改过后的共享变量的值,以及...
  • 下面的表格列展了.NET对协调或同步线程动作的可用的工具: 简易阻止方法 构成 目的 Sleep 阻止给定的时间周期 Join 等待另一个线程完成 锁系统 构成 目的 跨进程? ...
  • C#中的线程(二) 线程同步基础

    千次阅读 2011-12-16 10:37:57
    C#中的线程(二) 线程同步基础 1.同步要领   下面的表格列展了.NET对协调或同步线程动作的可用的工具:  简易阻止方法 构成 目的 Sleep 阻止给定的时间周期 ...
  • C#中的线程(中)-线程同步

    千次阅读 2015-03-09 10:59:44
    下面的表格列展了.NET对协调或同步线程动作的可用的工具:  简易阻止方法 构成 目的 Sleep 阻止给定的时间周期 Join 等待另一个线程完成  锁系统 ...
  • RTEMS线程调度算法(RMS)详解

    千次阅读 2018-01-24 17:43:51
    RTEMS是以线程为基本调度单位的,调度算法基于优先级的抢占式线程调度,支持256个线程优先级。当然RTEMS值hi创建同等优先级线程,相同优先级的线程采用时间片轮转调度。调度器寻找下一个最高优先级就绪线程的时间是o...
  • 万字长文带你还原进程和线程

    千次阅读 2020-02-13 11:36:31
    我们平常说的进程和线程更多的是基于编程语言的角度来说的,那么你真的了解什么是线程和进程吗?那么我们就从操作系统的角度来了解一下什么是进程和线程。 进程 操作系统中最核心的概念就是 进程,进程是对正在运行...
  • C# 多线程同步

    千次阅读 2010-06-12 15:47:00
    C# 多线程同步
  • Linux内核线程

    千次阅读 2014-01-28 12:15:47
    内核线程是直接由内核本身启动的进程...l 周期性地将修改的内存页与页来源设备同步。 l 如果内存页很少使用,则写入交换区。 l 管理延时动作 l 实现文件系统的事务日志。   内核线程主要有两种类型: 1.
  • 第二部分:线程同步基础 同步要领 下面的表格列展了.NET对协调或同步线程动作的可用的工具: 简易阻止方法 构成 目的 Sleep 阻止给定的时间周期 Join ...
  • ThreadLocal 线程复用的问题

    千次阅读 2018-03-19 17:39:58
    Java中的ThreadLocal类...在我们日常 Web 开发中难免会遇到需要把一个参数层层的传递到最内的情况,但是中间可能根本不需要使用这个参数,因此这样我们完全没有必要在每一个方法里面都传递这样一个通用的参数。...
  • pthread多线程编程的学习小结

    万次阅读 2010-10-04 12:33:00
    pthread多线程编程整理=================================================================================pthread_mutex_lock 函数名pthread_mutex_lock, pthread_mutex_trylock, pthread_mutex_unlock - lock ...
  • ym——Java多线程(新)

    千次阅读 2014-08-17 20:04:52
    线程线程概念、两种实现方式的区别进程与线程 从计算机操作系统的发展来看,经历了这样的两个阶段 单线程处理:最传统的DOS系统中只要有病毒出现,则立即有反映,因为在DOS系统中属于单进程处理,即:在同一个...
  • 所谓模式就是脱离特定的例子使用更一般化的,通用化的表达方式来察看,描述,总结相同的问题.现在我们来研究这个模式:共享资源(sharedResource)参与者:在临界区模式中,一定有一个或一个以上的共享资源角色的参与.在上面...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 56,284
精华内容 22,513
关键字:

线程通用块层