/* *  Block device elevator/IO-scheduler. * *  Copyright (C) 2000 Andrea Arcangeli <andrea@suse.de> SuSE * * 30042000 Jens Axboe <axboe@suse.de> : * * Split the elevator a bit so that it is possible to choose a different * one or even write a new "plug in". There are three pieces: * - elevator_fn, inserts a new request in the queue list * - elevator_merge_fn, decides whether a new buffer can be merged with *   an existing request * - elevator_dequeue_fn, called when a request is taken off the active list * * 20082000 Dave Jones <davej@suse.de> : * Removed tests for max-bomb-segments, which was breaking elvtune *  when run without -bN * * Jens: * - Rework again to work with bio instead of buffer_heads * - loose bi_dev comparisons, partition handling is right now * - completely modularize elevator setup and teardown * */#include <linux/kernel.h>#include <linux/fs.h>#include <linux/blkdev.h>#include <linux/elevator.h>#include <linux/bio.h>#include <linux/config.h>#include <linux/module.h>#include <linux/slab.h>#include <linux/init.h>#include <linux/compiler.h>#include <linux/delay.h>#include <linux/blktrace_api.h> #include <asm/uaccess.h> static DEFINE_SPINLOCK(elv_list_lock);static LIST_HEAD(elv_list); /* * can we safely merge with this request? */inline int elv_rq_merge_ok(struct request *rq, struct bio *bio){	if (!rq_mergeable(rq))		return 0; 	/*	 * different data direction or already started, don't merge	 */	if (bio_data_dir(bio) != rq_data_dir(rq))		return 0; 	/*	 * same device and no special stuff set, merge is ok	 */	if (rq->rq_disk == bio->bi_bdev->bd_disk &&	    !rq->waiting && !rq->special)		return 1; 	return 0;}EXPORT_SYMBOL(elv_rq_merge_ok); static inline int elv_try_merge(struct request *__rq, struct bio *bio){	int ret = ELEVATOR_NO_MERGE; 	/*	 * we can merge and sequence is ok, check if it's possible	 */	if (elv_rq_merge_ok(__rq, bio)) {		if (__rq->sector + __rq->nr_sectors == bio->bi_sector)			ret = ELEVATOR_BACK_MERGE;		else if (__rq->sector - bio_sectors(bio) == bio->bi_sector)			ret = ELEVATOR_FRONT_MERGE;	} 	return ret;} static struct elevator_type *elevator_find(const char *name){	struct elevator_type *e = NULL;	struct list_head *entry; 	list_for_each(entry, &elv_list) {		struct elevator_type *__e; 		__e = list_entry(entry, struct elevator_type, list); 		if (!strcmp(__e->elevator_name, name)) {			e = __e;			break;		}	} 	return e;} static void elevator_put(struct elevator_type *e){	module_put(e->elevator_owner);} static struct elevator_type *elevator_get(const char *name){	struct elevator_type *e; 	spin_lock_irq(&elv_list_lock); 	e = elevator_find(name);	if (e && !try_module_get(e->elevator_owner))		e = NULL; 	spin_unlock_irq(&elv_list_lock); 	return e;} static void *elevator_init_queue(request_queue_t *q, struct elevator_queue *eq){	return eq->ops->elevator_init_fn(q, eq);} static void elevator_attach(request_queue_t *q, struct elevator_queue *eq,			   void *data){	q->elevator = eq;	eq->elevator_data = data;} static char chosen_elevator[16]; static int __init elevator_setup(char *str){	/*	 * Be backwards-compatible with previous kernels, so users	 * won't get the wrong elevator.	 */	if (!strcmp(str, "as"))		strcpy(chosen_elevator, "anticipatory");	else		strncpy(chosen_elevator, str, sizeof(chosen_elevator) - 1);	return 1;} __setup("elevator=", elevator_setup); static struct kobj_type elv_ktype; static elevator_t *elevator_alloc(struct elevator_type *e){	elevator_t *eq = kmalloc(sizeof(elevator_t), GFP_KERNEL);	if (eq) {		memset(eq, 0, sizeof(*eq));		eq->ops = &e->ops;		eq->elevator_type = e;		kobject_init(&eq->kobj);		snprintf(eq->kobj.name, KOBJ_NAME_LEN, "%s", "iosched");		eq->kobj.ktype = &elv_ktype;		mutex_init(&eq->sysfs_lock);	} else {		elevator_put(e);	}	return eq;} static void elevator_release(struct kobject *kobj){	elevator_t *e = container_of(kobj, elevator_t, kobj);	elevator_put(e->elevator_type);	kfree(e);} int elevator_init(request_queue_t *q, char *name){	struct elevator_type *e = NULL;	struct elevator_queue *eq;	int ret = 0;	void *data; 	INIT_LIST_HEAD(&q->queue_head);	q->last_merge = NULL;	q->end_sector = 0;	q->boundary_rq = NULL; 	if (name && !(e = elevator_get(name)))		return -EINVAL; 	if (!e && *chosen_elevator && !(e = elevator_get(chosen_elevator)))		printk("I/O scheduler %s not found\n", chosen_elevator); 	if (!e && !(e = elevator_get(CONFIG_DEFAULT_IOSCHED))) {		printk("Default I/O scheduler not found, using no-op\n");		e = elevator_get("noop");	} 	eq = elevator_alloc(e);	if (!eq)		return -ENOMEM; 	data = elevator_init_queue(q, eq);	if (!data) {		kobject_put(&eq->kobj);		return -ENOMEM;	} 	elevator_attach(q, eq, data);	return ret;} void elevator_exit(elevator_t *e){	mutex_lock(&e->sysfs_lock);	if (e->ops->elevator_exit_fn)		e->ops->elevator_exit_fn(e);	e->ops = NULL;	mutex_unlock(&e->sysfs_lock); 	kobject_put(&e->kobj);} /* * Insert rq into dispatch queue of q.  Queue lock must be held on * entry.  If sort != 0, rq is sort-inserted; otherwise, rq will be * appended to the dispatch queue.  To be used by specific elevators. */void elv_dispatch_sort(request_queue_t *q, struct request *rq){	sector_t boundary;	struct list_head *entry; 	if (q->last_merge == rq)		q->last_merge = NULL;	q->nr_sorted--; 	boundary = q->end_sector; 	list_for_each_prev(entry, &q->queue_head) {		struct request *pos = list_entry_rq(entry); 		if (pos->flags & (REQ_SOFTBARRIER|REQ_HARDBARRIER|REQ_STARTED))			break;		if (rq->sector >= boundary) {			if (pos->sector < boundary)				continue;		} else {			if (pos->sector >= boundary)				break;		}		if (rq->sector >= pos->sector)			break;	} 	list_add(&rq->queuelist, entry);} int elv_merge(request_queue_t *q, struct request **req, struct bio *bio){	elevator_t *e = q->elevator;	int ret; 	if (q->last_merge) {		ret = elv_try_merge(q->last_merge, bio);		if (ret != ELEVATOR_NO_MERGE) {			*req = q->last_merge;			return ret;		}	} 	if (e->ops->elevator_merge_fn)		return e->ops->elevator_merge_fn(q, req, bio); 	return ELEVATOR_NO_MERGE;} void elv_merged_request(request_queue_t *q, struct request *rq){	elevator_t *e = q->elevator; 	if (e->ops->elevator_merged_fn)		e->ops->elevator_merged_fn(q, rq); 	q->last_merge = rq;} void elv_merge_requests(request_queue_t *q, struct request *rq,			     struct request *next){	elevator_t *e = q->elevator; 	if (e->ops->elevator_merge_req_fn)		e->ops->elevator_merge_req_fn(q, rq, next);	q->nr_sorted--; 	q->last_merge = rq;} void elv_requeue_request(request_queue_t *q, struct request *rq){	elevator_t *e = q->elevator; 	/*	 * it already went through dequeue, we need to decrement the	 * in_flight count again	 */	if (blk_account_rq(rq)) {		q->in_flight--;		if (blk_sorted_rq(rq) && e->ops->elevator_deactivate_req_fn)			e->ops->elevator_deactivate_req_fn(q, rq);	} 	rq->flags &= ~REQ_STARTED; 	elv_insert(q, rq, ELEVATOR_INSERT_REQUEUE);} static void elv_drain_elevator(request_queue_t *q){	static int printed;	while (q->elevator->ops->elevator_dispatch_fn(q, 1))		;	if (q->nr_sorted == 0)		return;	if (printed++ < 10) {		printk(KERN_ERR "%s: forced dispatching is broken "		       "(nr_sorted=%u), please report this\n",		       q->elevator->elevator_type->elevator_name, q->nr_sorted);	}} void elv_insert(request_queue_t *q, struct request *rq, int where){	struct list_head *pos;	unsigned ordseq;	int unplug_it = 1; 	blk_add_trace_rq(q, rq, BLK_TA_INSERT); 	rq->q = q; 	switch (where) {	case ELEVATOR_INSERT_FRONT:		rq->flags |= REQ_SOFTBARRIER; 		list_add(&rq->queuelist, &q->queue_head);		break; 	case ELEVATOR_INSERT_BACK:		rq->flags |= REQ_SOFTBARRIER;		elv_drain_elevator(q);		list_add_tail(&rq->queuelist, &q->queue_head);		/*		 * We kick the queue here for the following reasons.		 * - The elevator might have returned NULL previously		 *   to delay requests and returned them now.  As the		 *   queue wasn't empty before this request, ll_rw_blk		 *   won't run the queue on return, resulting in hang.		 * - Usually, back inserted requests won't be merged		 *   with anything.  There's no point in delaying queue		 *   processing.		 */		blk_remove_plug(q);		q->request_fn(q);		break; 	case ELEVATOR_INSERT_SORT:		BUG_ON(!blk_fs_request(rq));		rq->flags |= REQ_SORTED;		q->nr_sorted++;		if (q->last_merge == NULL && rq_mergeable(rq))			q->last_merge = rq;		/*		 * Some ioscheds (cfq) run q->request_fn directly, so		 * rq cannot be accessed after calling		 * elevator_add_req_fn.		 */		q->elevator->ops->elevator_add_req_fn(q, rq);		break; 	case ELEVATOR_INSERT_REQUEUE:		/*		 * If ordered flush isn't in progress, we do front		 * insertion; otherwise, requests should be requeued		 * in ordseq order.		 */		rq->flags |= REQ_SOFTBARRIER; 		if (q->ordseq == 0) {			list_add(&rq->queuelist, &q->queue_head);			break;		} 		ordseq = blk_ordered_req_seq(rq); 		list_for_each(pos, &q->queue_head) {			struct request *pos_rq = list_entry_rq(pos);			if (ordseq <= blk_ordered_req_seq(pos_rq))				break;		} 		list_add_tail(&rq->queuelist, pos);		/*		 * most requeues happen because of a busy condition, don't		 * force unplug of the queue for that case.		 */		unplug_it = 0;		break; 	default:		printk(KERN_ERR "%s: bad insertion point %d\n",		       __FUNCTION__, where);		BUG();	} 	if (unplug_it && blk_queue_plugged(q)) {		int nrq = q->rq.count[READ] + q->rq.count[WRITE]			- q->in_flight; 		if (nrq >= q->unplug_thresh)			__generic_unplug_device(q);	}} void __elv_add_request(request_queue_t *q, struct request *rq, int where,		       int plug){	if (q->ordcolor)		rq->flags |= REQ_ORDERED_COLOR; 	if (rq->flags & (REQ_SOFTBARRIER | REQ_HARDBARRIER)) {		/*		 * toggle ordered color		 */		if (blk_barrier_rq(rq))			q->ordcolor ^= 1; 		/*		 * barriers implicitly indicate back insertion		 */		if (where == ELEVATOR_INSERT_SORT)			where = ELEVATOR_INSERT_BACK; 		/*		 * this request is scheduling boundary, update		 * end_sector		 */		if (blk_fs_request(rq)) {			q->end_sector = rq_end_sector(rq);			q->boundary_rq = rq;		}	} else if (!(rq->flags & REQ_ELVPRIV) && where == ELEVATOR_INSERT_SORT)		where = ELEVATOR_INSERT_BACK; 	if (plug)		blk_plug_device(q); 	elv_insert(q, rq, where);} void elv_add_request(request_queue_t *q, struct request *rq, int where,		     int plug){	unsigned long flags; 	spin_lock_irqsave(q->queue_lock, flags);	__elv_add_request(q, rq, where, plug);	spin_unlock_irqrestore(q->queue_lock, flags);} static inline struct request *__elv_next_request(request_queue_t *q){	struct request *rq; 	while (1) {		while (!list_empty(&q->queue_head)) {			rq = list_entry_rq(q->queue_head.next);			if (blk_do_ordered(q, &rq))				return rq;		} 		if (!q->elevator->ops->elevator_dispatch_fn(q, 0))			return NULL;	}} struct request *elv_next_request(request_queue_t *q){	struct request *rq;	int ret; 	while ((rq = __elv_next_request(q)) != NULL) {		if (!(rq->flags & REQ_STARTED)) {			elevator_t *e = q->elevator; 			/*

Lines 1–500 of 921. Load more