dd->last_sector = drq->request->sector + drq->request->nr_sectors;	/*	 * take it off the sort and fifo list, move	 * to dispatch queue	 */	deadline_move_to_dispatch(dd, drq);}#define list_entry_fifo(ptr)	list_entry((ptr), struct deadline_rq, fifo)/* * deadline_check_fifo returns 0 if there are no expired reads on the fifo, * 1 otherwise. Requires !list_empty(&dd->fifo_list[data_dir]) */static inline int deadline_check_fifo(struct deadline_data *dd, int ddir){	struct deadline_rq *drq = list_entry_fifo(dd->fifo_list[ddir].next);	/*	 * drq is expired!	 */	if (time_after(jiffies, drq->expires))		return 1;	return 0;}/* * deadline_dispatch_requests selects the best request according to * read/write expire, fifo_batch, etc */static int deadline_dispatch_requests(struct deadline_data *dd){	const int reads = !list_empty(&dd->fifo_list[READ]);	const int writes = !list_empty(&dd->fifo_list[WRITE]);	struct deadline_rq *drq;	int data_dir, other_dir;	/*	 * batches are currently reads XOR writes	 */	drq = NULL;	if (dd->next_drq[READ])		drq = dd->next_drq[READ];	if (dd->next_drq[WRITE])		drq = dd->next_drq[WRITE];	if (drq) {		/* we have a "next request" */				if (dd->last_sector != drq->request->sector)			/* end the batch on a non sequential request */			dd->batching += dd->fifo_batch;				if (dd->batching < dd->fifo_batch)			/* we 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(&dd->sort_list[READ]));		if (writes && (dd->starved++ >= dd->writes_starved))			goto dispatch_writes;		data_dir = READ;		other_dir = WRITE;		goto dispatch_find_request;	}	/*	 * there are either no reads or writes have been starved	 */	if (writes) {dispatch_writes:		BUG_ON(RB_EMPTY(&dd->sort_list[WRITE]));		dd->starved = 0;		data_dir = WRITE;		other_dir = READ;		goto dispatch_find_request;	}	return 0;dispatch_find_request:	/*	 * we are not running a batch, find best request for selected data_dir	 */	if (deadline_check_fifo(dd, data_dir)) {		/* An expired request exists - satisfy it */		dd->batching = 0;		drq = list_entry_fifo(dd->fifo_list[data_dir].next);			} else if (dd->next_drq[data_dir]) {		/*		 * The last req was the same dir and we have a next request in		 * sort order. No expired requests so continue on from here.		 */		drq = dd->next_drq[data_dir];	} else {		/*		 * The last req was the other direction or we have run out of		 * higher-sectored requests. Go back to the lowest sectored		 * request (1 way elevator) and start a new batch.		 */		dd->batching = 0;		drq = deadline_find_first_drq(dd, data_dir);	}dispatch_request:	/*	 * drq is the selected appropriate request.	 */	dd->batching++;	deadline_move_request(dd, drq);	return 1;}static struct request *deadline_next_request(request_queue_t *q){	struct deadline_data *dd = q->elevator.elevator_data;	struct request *rq;	/*	 * if there are still requests on the dispatch queue, grab the first one	 */	if (!list_empty(dd->dispatch)) {dispatch:		rq = list_entry_rq(dd->dispatch->next);		return rq;	}	if (deadline_dispatch_requests(dd))		goto dispatch;	return NULL;}static voiddeadline_insert_request(request_queue_t *q, struct request *rq, int where){	struct deadline_data *dd = q->elevator.elevator_data;	/* barriers must flush the reorder queue */	if (unlikely(rq->flags & (REQ_SOFTBARRIER | REQ_HARDBARRIER)			&& where == ELEVATOR_INSERT_SORT))		where = ELEVATOR_INSERT_BACK;	switch (where) {		case ELEVATOR_INSERT_BACK:			while (deadline_dispatch_requests(dd))				;			list_add_tail(&rq->queuelist, dd->dispatch);			break;		case ELEVATOR_INSERT_FRONT:			list_add(&rq->queuelist, dd->dispatch);			break;		case ELEVATOR_INSERT_SORT:			BUG_ON(!blk_fs_request(rq));			deadline_add_request(q, rq);			break;		default:			printk("%s: bad insert point %d\n", __FUNCTION__,where);			return;	}}static int deadline_queue_empty(request_queue_t *q){	struct deadline_data *dd = q->elevator.elevator_data;	if (!list_empty(&dd->fifo_list[WRITE])	    || !list_empty(&dd->fifo_list[READ])	    || !list_empty(dd->dispatch))		return 0;	return 1;}static struct request *deadline_former_request(request_queue_t *q, struct request *rq){	struct deadline_rq *drq = RQ_DATA(rq);	struct rb_node *rbprev = rb_prev(&drq->rb_node);	if (rbprev)		return rb_entry_drq(rbprev)->request;	return NULL;}static struct request *deadline_latter_request(request_queue_t *q, struct request *rq){	struct deadline_rq *drq = RQ_DATA(rq);	struct rb_node *rbnext = rb_next(&drq->rb_node);	if (rbnext)		return rb_entry_drq(rbnext)->request;	return NULL;}static void deadline_exit(request_queue_t *q, elevator_t *e){	struct deadline_data *dd = e->elevator_data;	BUG_ON(!list_empty(&dd->fifo_list[READ]));	BUG_ON(!list_empty(&dd->fifo_list[WRITE]));	mempool_destroy(dd->drq_pool);	kfree(dd->hash);	kfree(dd);}/* * initialize elevator private data (deadline_data), and alloc a drq for * each request on the free lists */static int deadline_init(request_queue_t *q, elevator_t *e){	struct deadline_data *dd;	int i;	if (!drq_pool)		return -ENOMEM;	dd = kmalloc(sizeof(*dd), GFP_KERNEL);	if (!dd)		return -ENOMEM;	memset(dd, 0, sizeof(*dd));	dd->hash = kmalloc(sizeof(struct list_head)*DL_HASH_ENTRIES,GFP_KERNEL);	if (!dd->hash) {		kfree(dd);		return -ENOMEM;	}	dd->drq_pool = mempool_create(BLKDEV_MIN_RQ, mempool_alloc_slab, mempool_free_slab, drq_pool);	if (!dd->drq_pool) {		kfree(dd->hash);		kfree(dd);		return -ENOMEM;	}	for (i = 0; i < DL_HASH_ENTRIES; i++)		INIT_LIST_HEAD(&dd->hash[i]);	INIT_LIST_HEAD(&dd->fifo_list[READ]);	INIT_LIST_HEAD(&dd->fifo_list[WRITE]);	dd->sort_list[READ] = RB_ROOT;	dd->sort_list[WRITE] = RB_ROOT;	dd->dispatch = &q->queue_head;	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;	e->elevator_data = dd;	return 0;}static void deadline_put_request(request_queue_t *q, struct request *rq){	struct deadline_data *dd = q->elevator.elevator_data;	struct deadline_rq *drq = RQ_DATA(rq);	if (drq) {		mempool_free(drq, dd->drq_pool);		rq->elevator_private = NULL;	}}static intdeadline_set_request(request_queue_t *q, struct request *rq, int gfp_mask){	struct deadline_data *dd = q->elevator.elevator_data;	struct deadline_rq *drq;	drq = mempool_alloc(dd->drq_pool, gfp_mask);	if (drq) {		memset(drq, 0, sizeof(*drq));		RB_CLEAR(&drq->rb_node);		drq->request = rq;		INIT_LIST_HEAD(&drq->hash);		drq->on_hash = 0;		INIT_LIST_HEAD(&drq->fifo);		rq->elevator_private = drq;		return 0;	}	return 1;}/* * sysfs parts below */struct deadline_fs_entry {	struct attribute attr;	ssize_t (*show)(struct deadline_data *, char *);	ssize_t (*store)(struct deadline_data *, const char *, size_t);};static ssize_tdeadline_var_show(unsigned int var, char *page){	return sprintf(page, "%d\n", var);}static ssize_tdeadline_var_store(unsigned int *var, const char *page, size_t count){	char *p = (char *) page;	*var = simple_strtoul(p, &p, 10);	return count;}#define SHOW_FUNCTION(__FUNC, __VAR)					\static ssize_t __FUNC(struct deadline_data *dd, char *page)		\{									\	return deadline_var_show(__VAR, (page));			\}SHOW_FUNCTION(deadline_readexpire_show, dd->fifo_expire[READ]);SHOW_FUNCTION(deadline_writeexpire_show, dd->fifo_expire[WRITE]);SHOW_FUNCTION(deadline_writesstarved_show, dd->writes_starved);SHOW_FUNCTION(deadline_frontmerges_show, dd->front_merges);SHOW_FUNCTION(deadline_fifobatch_show, dd->fifo_batch);#undef SHOW_FUNCTION#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX)				\static ssize_t __FUNC(struct deadline_data *dd, const char *page, size_t count)	\{									\	int ret = deadline_var_store(__PTR, (page), count);		\	if (*(__PTR) < (MIN))						\		*(__PTR) = (MIN);					\	else if (*(__PTR) > (MAX))					\		*(__PTR) = (MAX);					\	return ret;							\}STORE_FUNCTION(deadline_readexpire_store, &dd->fifo_expire[READ], 0, INT_MAX);STORE_FUNCTION(deadline_writeexpire_store, &dd->fifo_expire[WRITE], 0, INT_MAX);STORE_FUNCTION(deadline_writesstarved_store, &dd->writes_starved, INT_MIN, INT_MAX);STORE_FUNCTION(deadline_frontmerges_store, &dd->front_merges, 0, 1);STORE_FUNCTION(deadline_fifobatch_store, &dd->fifo_batch, 0, INT_MAX);#undef STORE_FUNCTIONstatic struct deadline_fs_entry deadline_readexpire_entry = {	.attr = {.name = "read_expire", .mode = S_IRUGO | S_IWUSR },	.show = deadline_readexpire_show,	.store = deadline_readexpire_store,};static struct deadline_fs_entry deadline_writeexpire_entry = {	.attr = {.name = "write_expire", .mode = S_IRUGO | S_IWUSR },	.show = deadline_writeexpire_show,	.store = deadline_writeexpire_store,};static struct deadline_fs_entry deadline_writesstarved_entry = {	.attr = {.name = "writes_starved", .mode = S_IRUGO | S_IWUSR },	.show = deadline_writesstarved_show,	.store = deadline_writesstarved_store,};static struct deadline_fs_entry deadline_frontmerges_entry = {	.attr = {.name = "front_merges", .mode = S_IRUGO | S_IWUSR },	.show = deadline_frontmerges_show,	.store = deadline_frontmerges_store,};static struct deadline_fs_entry deadline_fifobatch_entry = {	.attr = {.name = "fifo_batch", .mode = S_IRUGO | S_IWUSR },	.show = deadline_fifobatch_show,	.store = deadline_fifobatch_store,};static struct attribute *default_attrs[] = {	&deadline_readexpire_entry.attr,	&deadline_writeexpire_entry.attr,	&deadline_writesstarved_entry.attr,	&deadline_frontmerges_entry.attr,	&deadline_fifobatch_entry.attr,	NULL,};#define to_deadline(atr) container_of((atr), struct deadline_fs_entry, attr)static ssize_tdeadline_attr_show(struct kobject *kobj, struct attribute *attr, char *page){	elevator_t *e = container_of(kobj, elevator_t, kobj);	struct deadline_fs_entry *entry = to_deadline(attr);	if (!entry->show)		return 0;	return entry->show(e->elevator_data, page);}static ssize_tdeadline_attr_store(struct kobject *kobj, struct attribute *attr,		    const char *page, size_t length){	elevator_t *e = container_of(kobj, elevator_t, kobj);	struct deadline_fs_entry *entry = to_deadline(attr);	if (!entry->store)		return -EINVAL;	return entry->store(e->elevator_data, page, length);}static struct sysfs_ops deadline_sysfs_ops = {	.show	= deadline_attr_show,	.store	= deadline_attr_store,};struct kobj_type deadline_ktype = {	.sysfs_ops	= &deadline_sysfs_ops,	.default_attrs	= default_attrs,};static int __init deadline_slab_setup(void){	drq_pool = kmem_cache_create("deadline_drq", sizeof(struct deadline_rq),				     0, 0, NULL, NULL);	if (!drq_pool)		panic("deadline: can't init slab pool\n");	return 0;}subsys_initcall(deadline_slab_setup);elevator_t iosched_deadline = {	.elevator_merge_fn = 		deadline_merge,	.elevator_merged_fn =		deadline_merged_request,	.elevator_merge_req_fn =	deadline_merged_requests,	.elevator_next_req_fn =		deadline_next_request,	.elevator_add_req_fn =		deadline_insert_request,	.elevator_remove_req_fn =	deadline_remove_request,	.elevator_queue_empty_fn =	deadline_queue_empty,	.elevator_former_req_fn =	deadline_former_request,	.elevator_latter_req_fn =	deadline_latter_request,	.elevator_set_req_fn =		deadline_set_request,	.elevator_put_req_fn = 		deadline_put_request,	.elevator_init_fn =		deadline_init,	.elevator_exit_fn =		deadline_exit,	.elevator_ktype =		&deadline_ktype,	.elevator_name =		"deadline",};EXPORT_SYMBOL(iosched_deadline);