elevator.c 26.4 KB
Newer Older
L
Linus Torvalds 已提交
1 2 3 4 5
/*
 *  Block device elevator/IO-scheduler.
 *
 *  Copyright (C) 2000 Andrea Arcangeli <andrea@suse.de> SuSE
 *
6
 * 30042000 Jens Axboe <axboe@kernel.dk> :
L
Linus Torvalds 已提交
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
 *
 * 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/module.h>
#include <linux/slab.h>
#include <linux/init.h>
#include <linux/compiler.h>
T
Tejun Heo 已提交
34
#include <linux/delay.h>
35
#include <linux/blktrace_api.h>
36
#include <linux/hash.h>
L
Linus Torvalds 已提交
37 38 39 40 41 42

#include <asm/uaccess.h>

static DEFINE_SPINLOCK(elv_list_lock);
static LIST_HEAD(elv_list);

43 44 45 46 47
/*
 * Merge hash stuff.
 */
static const int elv_hash_shift = 6;
#define ELV_HASH_BLOCK(sec)	((sec) >> 3)
48 49
#define ELV_HASH_FN(sec)	\
		(hash_long(ELV_HASH_BLOCK((sec)), elv_hash_shift))
50 51 52 53
#define ELV_HASH_ENTRIES	(1 << elv_hash_shift)
#define rq_hash_key(rq)		((rq)->sector + (rq)->nr_sectors)
#define ELV_ON_HASH(rq)		(!hlist_unhashed(&(rq)->hash))

54 55 56 57 58 59
/*
 * Query io scheduler to see if the current process issuing bio may be
 * merged with rq.
 */
static int elv_iosched_allow_merge(struct request *rq, struct bio *bio)
{
60
	struct request_queue *q = rq->q;
61 62 63 64 65 66 67 68
	elevator_t *e = q->elevator;

	if (e->ops->elevator_allow_merge_fn)
		return e->ops->elevator_allow_merge_fn(q, rq, bio);

	return 1;
}

L
Linus Torvalds 已提交
69 70 71
/*
 * can we safely merge with this request?
 */
72
int elv_rq_merge_ok(struct request *rq, struct bio *bio)
L
Linus Torvalds 已提交
73 74 75 76
{
	if (!rq_mergeable(rq))
		return 0;

77 78 79 80 81 82
	/*
	 * Don't merge file system requests and discard requests
	 */
	if (bio_discard(bio) != bio_discard(rq->bio))
		return 0;

L
Linus Torvalds 已提交
83 84 85 86 87 88 89
	/*
	 * different data direction or already started, don't merge
	 */
	if (bio_data_dir(bio) != rq_data_dir(rq))
		return 0;

	/*
90
	 * must be same device and not a special request
L
Linus Torvalds 已提交
91
	 */
92
	if (rq->rq_disk != bio->bi_bdev->bd_disk || rq->special)
93 94
		return 0;

95 96 97 98 99 100
	/*
	 * only merge integrity protected bio into ditto rq
	 */
	if (bio_integrity(bio) != blk_integrity_rq(rq))
		return 0;

101 102
	if (!elv_iosched_allow_merge(rq, bio))
		return 0;
L
Linus Torvalds 已提交
103

104
	return 1;
L
Linus Torvalds 已提交
105 106 107
}
EXPORT_SYMBOL(elv_rq_merge_ok);

108
static inline int elv_try_merge(struct request *__rq, struct bio *bio)
L
Linus Torvalds 已提交
109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126
{
	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)
{
127
	struct elevator_type *e;
L
Linus Torvalds 已提交
128

129
	list_for_each_entry(e, &elv_list, list) {
130 131
		if (!strcmp(e->elevator_name, name))
			return e;
L
Linus Torvalds 已提交
132 133
	}

134
	return NULL;
L
Linus Torvalds 已提交
135 136 137 138 139 140 141 142 143
}

static void elevator_put(struct elevator_type *e)
{
	module_put(e->elevator_owner);
}

static struct elevator_type *elevator_get(const char *name)
{
144
	struct elevator_type *e;
L
Linus Torvalds 已提交
145

146
	spin_lock(&elv_list_lock);
147 148

	e = elevator_find(name);
149 150 151 152 153 154 155 156 157 158
	if (!e) {
		char elv[ELV_NAME_MAX + strlen("-iosched")];

		spin_unlock(&elv_list_lock);

		if (!strcmp(name, "anticipatory"))
			sprintf(elv, "as-iosched");
		else
			sprintf(elv, "%s-iosched", name);

159
		request_module("%s", elv);
160 161 162 163
		spin_lock(&elv_list_lock);
		e = elevator_find(name);
	}

164 165 166
	if (e && !try_module_get(e->elevator_owner))
		e = NULL;

167
	spin_unlock(&elv_list_lock);
L
Linus Torvalds 已提交
168 169 170 171

	return e;
}

172 173
static void *elevator_init_queue(struct request_queue *q,
				 struct elevator_queue *eq)
L
Linus Torvalds 已提交
174
{
175
	return eq->ops->elevator_init_fn(q);
J
Jens Axboe 已提交
176
}
L
Linus Torvalds 已提交
177

178
static void elevator_attach(struct request_queue *q, struct elevator_queue *eq,
J
Jens Axboe 已提交
179 180
			   void *data)
{
L
Linus Torvalds 已提交
181
	q->elevator = eq;
J
Jens Axboe 已提交
182
	eq->elevator_data = data;
L
Linus Torvalds 已提交
183 184 185 186
}

static char chosen_elevator[16];

187
static int __init elevator_setup(char *str)
L
Linus Torvalds 已提交
188
{
189 190 191 192
	/*
	 * Be backwards-compatible with previous kernels, so users
	 * won't get the wrong elevator.
	 */
193
	if (!strcmp(str, "as"))
194
		strcpy(chosen_elevator, "anticipatory");
Z
Zachary Amsden 已提交
195
	else
196
		strncpy(chosen_elevator, str, sizeof(chosen_elevator) - 1);
197
	return 1;
L
Linus Torvalds 已提交
198 199 200 201
}

__setup("elevator=", elevator_setup);

202 203
static struct kobj_type elv_ktype;

204 205
static elevator_t *elevator_alloc(struct request_queue *q,
				  struct elevator_type *e)
206
{
207 208 209
	elevator_t *eq;
	int i;

210
	eq = kmalloc_node(sizeof(elevator_t), GFP_KERNEL | __GFP_ZERO, q->node);
211 212 213 214 215
	if (unlikely(!eq))
		goto err;

	eq->ops = &e->ops;
	eq->elevator_type = e;
216
	kobject_init(&eq->kobj, &elv_ktype);
217 218
	mutex_init(&eq->sysfs_lock);

219 220
	eq->hash = kmalloc_node(sizeof(struct hlist_head) * ELV_HASH_ENTRIES,
					GFP_KERNEL, q->node);
221 222 223 224 225 226
	if (!eq->hash)
		goto err;

	for (i = 0; i < ELV_HASH_ENTRIES; i++)
		INIT_HLIST_HEAD(&eq->hash[i]);

227
	return eq;
228 229 230 231
err:
	kfree(eq);
	elevator_put(e);
	return NULL;
232 233 234 235 236
}

static void elevator_release(struct kobject *kobj)
{
	elevator_t *e = container_of(kobj, elevator_t, kobj);
237

238
	elevator_put(e->elevator_type);
239
	kfree(e->hash);
240 241 242
	kfree(e);
}

243
int elevator_init(struct request_queue *q, char *name)
L
Linus Torvalds 已提交
244 245 246 247
{
	struct elevator_type *e = NULL;
	struct elevator_queue *eq;
	int ret = 0;
J
Jens Axboe 已提交
248
	void *data;
L
Linus Torvalds 已提交
249

T
Tejun Heo 已提交
250 251 252 253 254
	INIT_LIST_HEAD(&q->queue_head);
	q->last_merge = NULL;
	q->end_sector = 0;
	q->boundary_rq = NULL;

255 256 257 258 259
	if (name) {
		e = elevator_get(name);
		if (!e)
			return -EINVAL;
	}
L
Linus Torvalds 已提交
260

261 262 263 264 265 266
	if (!e && *chosen_elevator) {
		e = elevator_get(chosen_elevator);
		if (!e)
			printk(KERN_ERR "I/O scheduler %s not found\n",
							chosen_elevator);
	}
267

268 269 270 271 272 273 274 275
	if (!e) {
		e = elevator_get(CONFIG_DEFAULT_IOSCHED);
		if (!e) {
			printk(KERN_ERR
				"Default I/O scheduler not found. " \
				"Using noop.\n");
			e = elevator_get("noop");
		}
276 277
	}

278
	eq = elevator_alloc(q, e);
279
	if (!eq)
L
Linus Torvalds 已提交
280 281
		return -ENOMEM;

J
Jens Axboe 已提交
282 283
	data = elevator_init_queue(q, eq);
	if (!data) {
284
		kobject_put(&eq->kobj);
J
Jens Axboe 已提交
285 286
		return -ENOMEM;
	}
L
Linus Torvalds 已提交
287

J
Jens Axboe 已提交
288
	elevator_attach(q, eq, data);
L
Linus Torvalds 已提交
289 290
	return ret;
}
291 292
EXPORT_SYMBOL(elevator_init);

L
Linus Torvalds 已提交
293 294
void elevator_exit(elevator_t *e)
{
295
	mutex_lock(&e->sysfs_lock);
L
Linus Torvalds 已提交
296 297
	if (e->ops->elevator_exit_fn)
		e->ops->elevator_exit_fn(e);
298 299
	e->ops = NULL;
	mutex_unlock(&e->sysfs_lock);
L
Linus Torvalds 已提交
300

301
	kobject_put(&e->kobj);
L
Linus Torvalds 已提交
302
}
303 304
EXPORT_SYMBOL(elevator_exit);

305
static void elv_activate_rq(struct request_queue *q, struct request *rq)
306 307 308 309 310 311 312
{
	elevator_t *e = q->elevator;

	if (e->ops->elevator_activate_req_fn)
		e->ops->elevator_activate_req_fn(q, rq);
}

313
static void elv_deactivate_rq(struct request_queue *q, struct request *rq)
314 315 316 317 318 319 320
{
	elevator_t *e = q->elevator;

	if (e->ops->elevator_deactivate_req_fn)
		e->ops->elevator_deactivate_req_fn(q, rq);
}

321 322 323 324 325
static inline void __elv_rqhash_del(struct request *rq)
{
	hlist_del_init(&rq->hash);
}

326
static void elv_rqhash_del(struct request_queue *q, struct request *rq)
327 328 329 330 331
{
	if (ELV_ON_HASH(rq))
		__elv_rqhash_del(rq);
}

332
static void elv_rqhash_add(struct request_queue *q, struct request *rq)
333 334 335 336 337 338 339
{
	elevator_t *e = q->elevator;

	BUG_ON(ELV_ON_HASH(rq));
	hlist_add_head(&rq->hash, &e->hash[ELV_HASH_FN(rq_hash_key(rq))]);
}

340
static void elv_rqhash_reposition(struct request_queue *q, struct request *rq)
341 342 343 344 345
{
	__elv_rqhash_del(rq);
	elv_rqhash_add(q, rq);
}

346
static struct request *elv_rqhash_find(struct request_queue *q, sector_t offset)
347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367
{
	elevator_t *e = q->elevator;
	struct hlist_head *hash_list = &e->hash[ELV_HASH_FN(offset)];
	struct hlist_node *entry, *next;
	struct request *rq;

	hlist_for_each_entry_safe(rq, entry, next, hash_list, hash) {
		BUG_ON(!ELV_ON_HASH(rq));

		if (unlikely(!rq_mergeable(rq))) {
			__elv_rqhash_del(rq);
			continue;
		}

		if (rq_hash_key(rq) == offset)
			return rq;
	}

	return NULL;
}

368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423
/*
 * RB-tree support functions for inserting/lookup/removal of requests
 * in a sorted RB tree.
 */
struct request *elv_rb_add(struct rb_root *root, struct request *rq)
{
	struct rb_node **p = &root->rb_node;
	struct rb_node *parent = NULL;
	struct request *__rq;

	while (*p) {
		parent = *p;
		__rq = rb_entry(parent, struct request, rb_node);

		if (rq->sector < __rq->sector)
			p = &(*p)->rb_left;
		else if (rq->sector > __rq->sector)
			p = &(*p)->rb_right;
		else
			return __rq;
	}

	rb_link_node(&rq->rb_node, parent, p);
	rb_insert_color(&rq->rb_node, root);
	return NULL;
}
EXPORT_SYMBOL(elv_rb_add);

void elv_rb_del(struct rb_root *root, struct request *rq)
{
	BUG_ON(RB_EMPTY_NODE(&rq->rb_node));
	rb_erase(&rq->rb_node, root);
	RB_CLEAR_NODE(&rq->rb_node);
}
EXPORT_SYMBOL(elv_rb_del);

struct request *elv_rb_find(struct rb_root *root, sector_t sector)
{
	struct rb_node *n = root->rb_node;
	struct request *rq;

	while (n) {
		rq = rb_entry(n, struct request, rb_node);

		if (sector < rq->sector)
			n = n->rb_left;
		else if (sector > rq->sector)
			n = n->rb_right;
		else
			return rq;
	}

	return NULL;
}
EXPORT_SYMBOL(elv_rb_find);

424 425
/*
 * Insert rq into dispatch queue of q.  Queue lock must be held on
U
Uwe Kleine-König 已提交
426
 * entry.  rq is sort instead into the dispatch queue. To be used by
427
 * specific elevators.
428
 */
429
void elv_dispatch_sort(struct request_queue *q, struct request *rq)
430 431 432
{
	sector_t boundary;
	struct list_head *entry;
433
	int stop_flags;
434

435 436
	if (q->last_merge == rq)
		q->last_merge = NULL;
437 438 439

	elv_rqhash_del(q, rq);

440
	q->nr_sorted--;
441

J
Jens Axboe 已提交
442
	boundary = q->end_sector;
443
	stop_flags = REQ_SOFTBARRIER | REQ_HARDBARRIER | REQ_STARTED;
444 445 446
	list_for_each_prev(entry, &q->queue_head) {
		struct request *pos = list_entry_rq(entry);

447 448
		if (blk_discard_rq(rq) != blk_discard_rq(pos))
			break;
449 450
		if (rq_data_dir(rq) != rq_data_dir(pos))
			break;
451
		if (pos->cmd_flags & stop_flags)
452 453 454 455 456 457 458 459 460 461 462 463 464 465
			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);
}
466 467
EXPORT_SYMBOL(elv_dispatch_sort);

468
/*
469 470 471
 * Insert rq into dispatch queue of q.  Queue lock must be held on
 * entry.  rq is added to the back of the dispatch queue. To be used by
 * specific elevators.
472 473 474 475 476 477 478 479 480 481 482 483 484 485
 */
void elv_dispatch_add_tail(struct request_queue *q, struct request *rq)
{
	if (q->last_merge == rq)
		q->last_merge = NULL;

	elv_rqhash_del(q, rq);

	q->nr_sorted--;

	q->end_sector = rq_end_sector(rq);
	q->boundary_rq = rq;
	list_add_tail(&rq->queuelist, &q->queue_head);
}
486 487
EXPORT_SYMBOL(elv_dispatch_add_tail);

488
int elv_merge(struct request_queue *q, struct request **req, struct bio *bio)
L
Linus Torvalds 已提交
489 490
{
	elevator_t *e = q->elevator;
491
	struct request *__rq;
492 493
	int ret;

494 495 496
	/*
	 * First try one-hit cache.
	 */
497 498 499 500 501 502 503
	if (q->last_merge) {
		ret = elv_try_merge(q->last_merge, bio);
		if (ret != ELEVATOR_NO_MERGE) {
			*req = q->last_merge;
			return ret;
		}
	}
L
Linus Torvalds 已提交
504

505 506 507
	if (blk_queue_nomerges(q))
		return ELEVATOR_NO_MERGE;

508 509 510 511 512 513 514 515 516
	/*
	 * See if our hash lookup can find a potential backmerge.
	 */
	__rq = elv_rqhash_find(q, bio->bi_sector);
	if (__rq && elv_rq_merge_ok(__rq, bio)) {
		*req = __rq;
		return ELEVATOR_BACK_MERGE;
	}

L
Linus Torvalds 已提交
517 518 519 520 521 522
	if (e->ops->elevator_merge_fn)
		return e->ops->elevator_merge_fn(q, req, bio);

	return ELEVATOR_NO_MERGE;
}

523
void elv_merged_request(struct request_queue *q, struct request *rq, int type)
L
Linus Torvalds 已提交
524 525 526 527
{
	elevator_t *e = q->elevator;

	if (e->ops->elevator_merged_fn)
528
		e->ops->elevator_merged_fn(q, rq, type);
529

530 531
	if (type == ELEVATOR_BACK_MERGE)
		elv_rqhash_reposition(q, rq);
532

533
	q->last_merge = rq;
L
Linus Torvalds 已提交
534 535
}

536
void elv_merge_requests(struct request_queue *q, struct request *rq,
L
Linus Torvalds 已提交
537 538 539 540 541 542
			     struct request *next)
{
	elevator_t *e = q->elevator;

	if (e->ops->elevator_merge_req_fn)
		e->ops->elevator_merge_req_fn(q, rq, next);
543

544 545 546 547
	elv_rqhash_reposition(q, rq);
	elv_rqhash_del(q, next);

	q->nr_sorted--;
548
	q->last_merge = rq;
L
Linus Torvalds 已提交
549 550
}

551
void elv_requeue_request(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
552 553 554 555 556
{
	/*
	 * it already went through dequeue, we need to decrement the
	 * in_flight count again
	 */
557
	if (blk_account_rq(rq)) {
L
Linus Torvalds 已提交
558
		q->in_flight--;
559 560
		if (blk_sorted_rq(rq))
			elv_deactivate_rq(q, rq);
561
	}
L
Linus Torvalds 已提交
562

563
	rq->cmd_flags &= ~REQ_STARTED;
L
Linus Torvalds 已提交
564

565
	elv_insert(q, rq, ELEVATOR_INSERT_REQUEUE);
L
Linus Torvalds 已提交
566 567
}

568
static void elv_drain_elevator(struct request_queue *q)
569 570 571 572 573 574 575 576 577 578 579 580 581
{
	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);
	}
}

582
void elv_insert(struct request_queue *q, struct request *rq, int where)
L
Linus Torvalds 已提交
583
{
584 585
	struct list_head *pos;
	unsigned ordseq;
J
Jens Axboe 已提交
586
	int unplug_it = 1;
587

588 589
	blk_add_trace_rq(q, rq, BLK_TA_INSERT);

L
Linus Torvalds 已提交
590 591
	rq->q = q;

592 593
	switch (where) {
	case ELEVATOR_INSERT_FRONT:
594
		rq->cmd_flags |= REQ_SOFTBARRIER;
595 596 597 598 599

		list_add(&rq->queuelist, &q->queue_head);
		break;

	case ELEVATOR_INSERT_BACK:
600
		rq->cmd_flags |= REQ_SOFTBARRIER;
601
		elv_drain_elevator(q);
602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617
		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:
618
		BUG_ON(!blk_fs_request(rq) && !blk_discard_rq(rq));
619
		rq->cmd_flags |= REQ_SORTED;
620
		q->nr_sorted++;
621 622 623 624 625 626
		if (rq_mergeable(rq)) {
			elv_rqhash_add(q, rq);
			if (!q->last_merge)
				q->last_merge = rq;
		}

627 628 629 630 631 632
		/*
		 * 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);
633 634
		break;

635 636 637 638 639 640
	case ELEVATOR_INSERT_REQUEUE:
		/*
		 * If ordered flush isn't in progress, we do front
		 * insertion; otherwise, requests should be requeued
		 * in ordseq order.
		 */
641
		rq->cmd_flags |= REQ_SOFTBARRIER;
642

643 644 645 646 647 648
		/*
		 * Most requeues happen because of a busy condition,
		 * don't force unplug of the queue for that case.
		 */
		unplug_it = 0;

649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664
		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);
		break;

665 666
	default:
		printk(KERN_ERR "%s: bad insertion point %d\n",
667
		       __func__, where);
668 669 670
		BUG();
	}

J
Jens Axboe 已提交
671
	if (unplug_it && blk_queue_plugged(q)) {
672 673 674 675 676 677
		int nrq = q->rq.count[READ] + q->rq.count[WRITE]
			- q->in_flight;

		if (nrq >= q->unplug_thresh)
			__generic_unplug_device(q);
	}
L
Linus Torvalds 已提交
678 679
}

680
void __elv_add_request(struct request_queue *q, struct request *rq, int where,
681 682 683
		       int plug)
{
	if (q->ordcolor)
684
		rq->cmd_flags |= REQ_ORDERED_COLOR;
685

686
	if (rq->cmd_flags & (REQ_SOFTBARRIER | REQ_HARDBARRIER)) {
687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702
		/*
		 * 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
		 */
703
		if (blk_fs_request(rq) || blk_discard_rq(rq)) {
704 705 706
			q->end_sector = rq_end_sector(rq);
			q->boundary_rq = rq;
		}
707 708
	} else if (!(rq->cmd_flags & REQ_ELVPRIV) &&
		    where == ELEVATOR_INSERT_SORT)
709 710 711 712 713 714 715
		where = ELEVATOR_INSERT_BACK;

	if (plug)
		blk_plug_device(q);

	elv_insert(q, rq, where);
}
716 717
EXPORT_SYMBOL(__elv_add_request);

718
void elv_add_request(struct request_queue *q, struct request *rq, int where,
L
Linus Torvalds 已提交
719 720 721 722 723 724 725 726
		     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);
}
727 728
EXPORT_SYMBOL(elv_add_request);

729
static inline struct request *__elv_next_request(struct request_queue *q)
L
Linus Torvalds 已提交
730
{
731 732
	struct request *rq;

733 734 735 736 737 738
	while (1) {
		while (!list_empty(&q->queue_head)) {
			rq = list_entry_rq(q->queue_head.next);
			if (blk_do_ordered(q, &rq))
				return rq;
		}
L
Linus Torvalds 已提交
739

740 741
		if (!q->elevator->ops->elevator_dispatch_fn(q, 0))
			return NULL;
L
Linus Torvalds 已提交
742 743 744
	}
}

745
struct request *elv_next_request(struct request_queue *q)
L
Linus Torvalds 已提交
746 747 748 749 750
{
	struct request *rq;
	int ret;

	while ((rq = __elv_next_request(q)) != NULL) {
751 752 753 754 755 756 757 758
		/*
		 * Kill the empty barrier place holder, the driver must
		 * not ever see it.
		 */
		if (blk_empty_barrier(rq)) {
			end_queued_request(rq, 1);
			continue;
		}
759
		if (!(rq->cmd_flags & REQ_STARTED)) {
760 761 762 763 764
			/*
			 * This is the first time the device driver
			 * sees this request (possibly after
			 * requeueing).  Notify IO scheduler.
			 */
765 766
			if (blk_sorted_rq(rq))
				elv_activate_rq(q, rq);
L
Linus Torvalds 已提交
767

768 769 770 771 772
			/*
			 * just mark as started even if we don't start
			 * it, a request that has been delayed should
			 * not be passed by new incoming requests
			 */
773
			rq->cmd_flags |= REQ_STARTED;
774
			blk_add_trace_rq(q, rq, BLK_TA_ISSUE);
775
		}
L
Linus Torvalds 已提交
776

777
		if (!q->boundary_rq || q->boundary_rq == rq) {
J
Jens Axboe 已提交
778
			q->end_sector = rq_end_sector(rq);
779 780
			q->boundary_rq = NULL;
		}
L
Linus Torvalds 已提交
781

J
James Bottomley 已提交
782 783 784 785 786 787 788 789 790 791 792 793 794 795
		if (rq->cmd_flags & REQ_DONTPREP)
			break;

		if (q->dma_drain_size && rq->data_len) {
			/*
			 * make sure space for the drain appears we
			 * know we can do this because max_hw_segments
			 * has been adjusted to be one fewer than the
			 * device can handle
			 */
			rq->nr_phys_segments++;
		}

		if (!q->prep_rq_fn)
L
Linus Torvalds 已提交
796 797 798 799 800 801
			break;

		ret = q->prep_rq_fn(q, rq);
		if (ret == BLKPREP_OK) {
			break;
		} else if (ret == BLKPREP_DEFER) {
802 803 804
			/*
			 * the request may have been (partially) prepped.
			 * we need to keep this request in the front to
805 806
			 * avoid resource deadlock.  REQ_STARTED will
			 * prevent other fs requests from passing this one.
807
			 */
J
James Bottomley 已提交
808 809 810 811 812 813 814 815 816
			if (q->dma_drain_size && rq->data_len &&
			    !(rq->cmd_flags & REQ_DONTPREP)) {
				/*
				 * remove the space for the drain we added
				 * so that we don't add it again
				 */
				--rq->nr_phys_segments;
			}

L
Linus Torvalds 已提交
817 818 819
			rq = NULL;
			break;
		} else if (ret == BLKPREP_KILL) {
820
			rq->cmd_flags |= REQ_QUIET;
821
			end_queued_request(rq, 0);
L
Linus Torvalds 已提交
822
		} else {
823
			printk(KERN_ERR "%s: bad return=%d\n", __func__, ret);
L
Linus Torvalds 已提交
824 825 826 827 828 829
			break;
		}
	}

	return rq;
}
830 831
EXPORT_SYMBOL(elv_next_request);

832
void elv_dequeue_request(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
833
{
834
	BUG_ON(list_empty(&rq->queuelist));
835
	BUG_ON(ELV_ON_HASH(rq));
836 837

	list_del_init(&rq->queuelist);
L
Linus Torvalds 已提交
838 839 840 841

	/*
	 * the time frame between a request being removed from the lists
	 * and to it is freed is accounted as io that is in progress at
842
	 * the driver side.
L
Linus Torvalds 已提交
843 844 845 846
	 */
	if (blk_account_rq(rq))
		q->in_flight++;
}
847 848
EXPORT_SYMBOL(elv_dequeue_request);

849
int elv_queue_empty(struct request_queue *q)
L
Linus Torvalds 已提交
850 851 852
{
	elevator_t *e = q->elevator;

853 854 855
	if (!list_empty(&q->queue_head))
		return 0;

L
Linus Torvalds 已提交
856 857 858
	if (e->ops->elevator_queue_empty_fn)
		return e->ops->elevator_queue_empty_fn(q);

859
	return 1;
L
Linus Torvalds 已提交
860
}
861 862
EXPORT_SYMBOL(elv_queue_empty);

863
struct request *elv_latter_request(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
864 865 866 867 868 869 870 871
{
	elevator_t *e = q->elevator;

	if (e->ops->elevator_latter_req_fn)
		return e->ops->elevator_latter_req_fn(q, rq);
	return NULL;
}

872
struct request *elv_former_request(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
873 874 875 876 877 878 879 880
{
	elevator_t *e = q->elevator;

	if (e->ops->elevator_former_req_fn)
		return e->ops->elevator_former_req_fn(q, rq);
	return NULL;
}

881
int elv_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask)
L
Linus Torvalds 已提交
882 883 884 885
{
	elevator_t *e = q->elevator;

	if (e->ops->elevator_set_req_fn)
886
		return e->ops->elevator_set_req_fn(q, rq, gfp_mask);
L
Linus Torvalds 已提交
887 888 889 890 891

	rq->elevator_private = NULL;
	return 0;
}

892
void elv_put_request(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
893 894 895 896
{
	elevator_t *e = q->elevator;

	if (e->ops->elevator_put_req_fn)
897
		e->ops->elevator_put_req_fn(rq);
L
Linus Torvalds 已提交
898 899
}

900
int elv_may_queue(struct request_queue *q, int rw)
L
Linus Torvalds 已提交
901 902 903 904
{
	elevator_t *e = q->elevator;

	if (e->ops->elevator_may_queue_fn)
905
		return e->ops->elevator_may_queue_fn(q, rw);
L
Linus Torvalds 已提交
906 907 908 909

	return ELV_MQUEUE_MAY;
}

910
void elv_completed_request(struct request_queue *q, struct request *rq)
L
Linus Torvalds 已提交
911 912 913 914 915 916
{
	elevator_t *e = q->elevator;

	/*
	 * request is released from the driver, io must be done
	 */
917
	if (blk_account_rq(rq)) {
L
Linus Torvalds 已提交
918
		q->in_flight--;
919 920 921
		if (blk_sorted_rq(rq) && e->ops->elevator_completed_req_fn)
			e->ops->elevator_completed_req_fn(q, rq);
	}
922

923 924 925 926 927 928 929
	/*
	 * Check if the queue is waiting for fs requests to be
	 * drained for flush sequence.
	 */
	if (unlikely(q->ordseq)) {
		struct request *first_rq = list_entry_rq(q->queue_head.next);
		if (q->in_flight == 0 &&
930 931 932 933 934
		    blk_ordered_cur_seq(q) == QUEUE_ORDSEQ_DRAIN &&
		    blk_ordered_req_seq(first_rq) > QUEUE_ORDSEQ_DRAIN) {
			blk_ordered_complete_seq(q, QUEUE_ORDSEQ_DRAIN, 0);
			q->request_fn(q);
		}
935
	}
L
Linus Torvalds 已提交
936 937
}

938 939 940 941
#define to_elv(atr) container_of((atr), struct elv_fs_entry, attr)

static ssize_t
elv_attr_show(struct kobject *kobj, struct attribute *attr, char *page)
L
Linus Torvalds 已提交
942
{
943 944 945 946 947 948 949 950 951 952 953 954
	elevator_t *e = container_of(kobj, elevator_t, kobj);
	struct elv_fs_entry *entry = to_elv(attr);
	ssize_t error;

	if (!entry->show)
		return -EIO;

	mutex_lock(&e->sysfs_lock);
	error = e->ops ? entry->show(e, page) : -ENOENT;
	mutex_unlock(&e->sysfs_lock);
	return error;
}
L
Linus Torvalds 已提交
955

956 957 958 959 960 961 962
static ssize_t
elv_attr_store(struct kobject *kobj, struct attribute *attr,
	       const char *page, size_t length)
{
	elevator_t *e = container_of(kobj, elevator_t, kobj);
	struct elv_fs_entry *entry = to_elv(attr);
	ssize_t error;
L
Linus Torvalds 已提交
963

964 965
	if (!entry->store)
		return -EIO;
L
Linus Torvalds 已提交
966

967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987
	mutex_lock(&e->sysfs_lock);
	error = e->ops ? entry->store(e, page, length) : -ENOENT;
	mutex_unlock(&e->sysfs_lock);
	return error;
}

static struct sysfs_ops elv_sysfs_ops = {
	.show	= elv_attr_show,
	.store	= elv_attr_store,
};

static struct kobj_type elv_ktype = {
	.sysfs_ops	= &elv_sysfs_ops,
	.release	= elevator_release,
};

int elv_register_queue(struct request_queue *q)
{
	elevator_t *e = q->elevator;
	int error;

988
	error = kobject_add(&e->kobj, &q->kobj, "%s", "iosched");
989
	if (!error) {
990
		struct elv_fs_entry *attr = e->elevator_type->elevator_attrs;
991
		if (attr) {
992 993
			while (attr->attr.name) {
				if (sysfs_create_file(&e->kobj, &attr->attr))
994
					break;
995
				attr++;
996 997 998 999 1000
			}
		}
		kobject_uevent(&e->kobj, KOBJ_ADD);
	}
	return error;
L
Linus Torvalds 已提交
1001 1002
}

J
Jens Axboe 已提交
1003 1004 1005 1006 1007 1008
static void __elv_unregister_queue(elevator_t *e)
{
	kobject_uevent(&e->kobj, KOBJ_REMOVE);
	kobject_del(&e->kobj);
}

L
Linus Torvalds 已提交
1009 1010
void elv_unregister_queue(struct request_queue *q)
{
J
Jens Axboe 已提交
1011 1012
	if (q)
		__elv_unregister_queue(q->elevator);
L
Linus Torvalds 已提交
1013 1014
}

1015
void elv_register(struct elevator_type *e)
L
Linus Torvalds 已提交
1016
{
1017
	char *def = "";
1018 1019

	spin_lock(&elv_list_lock);
1020
	BUG_ON(elevator_find(e->elevator_name));
L
Linus Torvalds 已提交
1021
	list_add_tail(&e->list, &elv_list);
1022
	spin_unlock(&elv_list_lock);
L
Linus Torvalds 已提交
1023

1024 1025 1026
	if (!strcmp(e->elevator_name, chosen_elevator) ||
			(!*chosen_elevator &&
			 !strcmp(e->elevator_name, CONFIG_DEFAULT_IOSCHED)))
1027 1028
				def = " (default)";

1029 1030
	printk(KERN_INFO "io scheduler %s registered%s\n", e->elevator_name,
								def);
L
Linus Torvalds 已提交
1031 1032 1033 1034 1035
}
EXPORT_SYMBOL_GPL(elv_register);

void elv_unregister(struct elevator_type *e)
{
1036 1037 1038 1039 1040
	struct task_struct *g, *p;

	/*
	 * Iterate every thread in the process to remove the io contexts.
	 */
1041 1042 1043 1044
	if (e->ops.trim) {
		read_lock(&tasklist_lock);
		do_each_thread(g, p) {
			task_lock(p);
1045 1046
			if (p->io_context)
				e->ops.trim(p->io_context);
1047 1048 1049 1050
			task_unlock(p);
		} while_each_thread(g, p);
		read_unlock(&tasklist_lock);
	}
1051

1052
	spin_lock(&elv_list_lock);
L
Linus Torvalds 已提交
1053
	list_del_init(&e->list);
1054
	spin_unlock(&elv_list_lock);
L
Linus Torvalds 已提交
1055 1056 1057 1058 1059 1060 1061
}
EXPORT_SYMBOL_GPL(elv_unregister);

/*
 * switch to new_e io scheduler. be careful not to introduce deadlocks -
 * we don't free the old io scheduler, before we have allocated what we
 * need for the new one. this way we have a chance of going back to the old
T
Tejun Heo 已提交
1062
 * one, if the new one fails init for some reason.
L
Linus Torvalds 已提交
1063
 */
1064
static int elevator_switch(struct request_queue *q, struct elevator_type *new_e)
L
Linus Torvalds 已提交
1065
{
T
Tejun Heo 已提交
1066
	elevator_t *old_elevator, *e;
J
Jens Axboe 已提交
1067
	void *data;
L
Linus Torvalds 已提交
1068

T
Tejun Heo 已提交
1069 1070 1071
	/*
	 * Allocate new elevator
	 */
1072
	e = elevator_alloc(q, new_e);
L
Linus Torvalds 已提交
1073
	if (!e)
1074
		return 0;
L
Linus Torvalds 已提交
1075

J
Jens Axboe 已提交
1076 1077 1078 1079 1080 1081
	data = elevator_init_queue(q, e);
	if (!data) {
		kobject_put(&e->kobj);
		return 0;
	}

L
Linus Torvalds 已提交
1082
	/*
T
Tejun Heo 已提交
1083
	 * Turn on BYPASS and drain all requests w/ elevator private data
L
Linus Torvalds 已提交
1084
	 */
T
Tejun Heo 已提交
1085 1086
	spin_lock_irq(q->queue_lock);

N
Nick Piggin 已提交
1087
	queue_flag_set(QUEUE_FLAG_ELVSWITCH, q);
T
Tejun Heo 已提交
1088

1089
	elv_drain_elevator(q);
T
Tejun Heo 已提交
1090 1091

	while (q->rq.elvpriv) {
1092 1093
		blk_remove_plug(q);
		q->request_fn(q);
T
Tejun Heo 已提交
1094
		spin_unlock_irq(q->queue_lock);
J
Jens Axboe 已提交
1095
		msleep(10);
T
Tejun Heo 已提交
1096
		spin_lock_irq(q->queue_lock);
1097
		elv_drain_elevator(q);
T
Tejun Heo 已提交
1098 1099
	}

L
Linus Torvalds 已提交
1100
	/*
J
Jens Axboe 已提交
1101
	 * Remember old elevator.
L
Linus Torvalds 已提交
1102 1103 1104 1105 1106 1107
	 */
	old_elevator = q->elevator;

	/*
	 * attach and start new elevator
	 */
J
Jens Axboe 已提交
1108 1109 1110 1111 1112
	elevator_attach(q, e, data);

	spin_unlock_irq(q->queue_lock);

	__elv_unregister_queue(old_elevator);
L
Linus Torvalds 已提交
1113 1114 1115 1116 1117

	if (elv_register_queue(q))
		goto fail_register;

	/*
T
Tejun Heo 已提交
1118
	 * finally exit old elevator and turn off BYPASS.
L
Linus Torvalds 已提交
1119 1120
	 */
	elevator_exit(old_elevator);
N
Nick Piggin 已提交
1121 1122 1123 1124
	spin_lock_irq(q->queue_lock);
	queue_flag_clear(QUEUE_FLAG_ELVSWITCH, q);
	spin_unlock_irq(q->queue_lock);

1125 1126
	blk_add_trace_msg(q, "elv switch: %s", e->elevator_type->elevator_name);

1127
	return 1;
L
Linus Torvalds 已提交
1128 1129 1130 1131 1132 1133 1134 1135 1136

fail_register:
	/*
	 * switch failed, exit the new io scheduler and reattach the old
	 * one again (along with re-adding the sysfs dir)
	 */
	elevator_exit(e);
	q->elevator = old_elevator;
	elv_register_queue(q);
N
Nick Piggin 已提交
1137 1138 1139 1140 1141

	spin_lock_irq(q->queue_lock);
	queue_flag_clear(QUEUE_FLAG_ELVSWITCH, q);
	spin_unlock_irq(q->queue_lock);

1142
	return 0;
L
Linus Torvalds 已提交
1143 1144
}

1145 1146
ssize_t elv_iosched_store(struct request_queue *q, const char *name,
			  size_t count)
L
Linus Torvalds 已提交
1147 1148
{
	char elevator_name[ELV_NAME_MAX];
1149
	size_t len;
L
Linus Torvalds 已提交
1150 1151
	struct elevator_type *e;

1152 1153 1154
	elevator_name[sizeof(elevator_name) - 1] = '\0';
	strncpy(elevator_name, name, sizeof(elevator_name) - 1);
	len = strlen(elevator_name);
L
Linus Torvalds 已提交
1155

1156 1157
	if (len && elevator_name[len - 1] == '\n')
		elevator_name[len - 1] = '\0';
L
Linus Torvalds 已提交
1158 1159 1160 1161 1162 1163 1164

	e = elevator_get(elevator_name);
	if (!e) {
		printk(KERN_ERR "elevator: type %s not found\n", elevator_name);
		return -EINVAL;
	}

1165 1166
	if (!strcmp(elevator_name, q->elevator->elevator_type->elevator_name)) {
		elevator_put(e);
L
Linus Torvalds 已提交
1167
		return count;
1168
	}
L
Linus Torvalds 已提交
1169

1170
	if (!elevator_switch(q, e))
1171 1172
		printk(KERN_ERR "elevator: switch to %s failed\n",
							elevator_name);
L
Linus Torvalds 已提交
1173 1174 1175
	return count;
}

1176
ssize_t elv_iosched_show(struct request_queue *q, char *name)
L
Linus Torvalds 已提交
1177 1178 1179
{
	elevator_t *e = q->elevator;
	struct elevator_type *elv = e->elevator_type;
1180
	struct elevator_type *__e;
L
Linus Torvalds 已提交
1181 1182
	int len = 0;

1183
	spin_lock(&elv_list_lock);
1184
	list_for_each_entry(__e, &elv_list, list) {
L
Linus Torvalds 已提交
1185 1186 1187 1188 1189
		if (!strcmp(elv->elevator_name, __e->elevator_name))
			len += sprintf(name+len, "[%s] ", elv->elevator_name);
		else
			len += sprintf(name+len, "%s ", __e->elevator_name);
	}
1190
	spin_unlock(&elv_list_lock);
L
Linus Torvalds 已提交
1191 1192 1193 1194 1195

	len += sprintf(len+name, "\n");
	return len;
}

1196 1197
struct request *elv_rb_former_request(struct request_queue *q,
				      struct request *rq)
1198 1199 1200 1201 1202 1203 1204 1205 1206 1207
{
	struct rb_node *rbprev = rb_prev(&rq->rb_node);

	if (rbprev)
		return rb_entry_rq(rbprev);

	return NULL;
}
EXPORT_SYMBOL(elv_rb_former_request);

1208 1209
struct request *elv_rb_latter_request(struct request_queue *q,
				      struct request *rq)
1210 1211 1212 1213 1214 1215 1216 1217 1218
{
	struct rb_node *rbnext = rb_next(&rq->rb_node);

	if (rbnext)
		return rb_entry_rq(rbnext);

	return NULL;
}
EXPORT_SYMBOL(elv_rb_latter_request);