deadline-iosched.c

Linux Kernel 2.6.9 for OMAP1710

	
	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 void
deadline_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 int
deadline_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_t
deadline_var_show(unsigned int var, char *page)
{
	return sprintf(page, "%d\n", var);
}

static ssize_t
deadline_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_FUNCTION

static 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_t
deadline_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_t
deadline_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);