elevator.c 24.5 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
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> :
Linus Torvalds's avatar
Linus Torvalds committed
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>
34
#include <linux/delay.h>
35
#include <linux/blktrace_api.h>
36
#include <linux/hash.h>
Linus Torvalds's avatar
Linus Torvalds committed
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 48 49 50 51 52
/*
 * Merge hash stuff.
 */
static const int elv_hash_shift = 6;
#define ELV_HASH_BLOCK(sec)	((sec) >> 3)
#define ELV_HASH_FN(sec)	(hash_long(ELV_HASH_BLOCK((sec)), elv_hash_shift))
#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))

Linus Torvalds's avatar
Linus Torvalds committed
53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69
/*
 * 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
	 */
70
	if (rq->rq_disk == bio->bi_bdev->bd_disk && !rq->special)
Linus Torvalds's avatar
Linus Torvalds committed
71 72 73 74 75 76
		return 1;

	return 0;
}
EXPORT_SYMBOL(elv_rq_merge_ok);

77
static inline int elv_try_merge(struct request *__rq, struct bio *bio)
Linus Torvalds's avatar
Linus Torvalds committed
78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119
{
	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)
{
120
	struct elevator_type *e;
Linus Torvalds's avatar
Linus Torvalds committed
121

122 123 124 125 126 127 128
	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);
Linus Torvalds's avatar
Linus Torvalds committed
129 130 131 132

	return e;
}

Jens Axboe's avatar
Jens Axboe committed
133
static void *elevator_init_queue(request_queue_t *q, struct elevator_queue *eq)
Linus Torvalds's avatar
Linus Torvalds committed
134
{
Jens Axboe's avatar
Jens Axboe committed
135 136
	return eq->ops->elevator_init_fn(q, eq);
}
Linus Torvalds's avatar
Linus Torvalds committed
137

Jens Axboe's avatar
Jens Axboe committed
138 139 140
static void elevator_attach(request_queue_t *q, struct elevator_queue *eq,
			   void *data)
{
Linus Torvalds's avatar
Linus Torvalds committed
141
	q->elevator = eq;
Jens Axboe's avatar
Jens Axboe committed
142
	eq->elevator_data = data;
Linus Torvalds's avatar
Linus Torvalds committed
143 144 145 146
}

static char chosen_elevator[16];

147
static int __init elevator_setup(char *str)
Linus Torvalds's avatar
Linus Torvalds committed
148
{
149 150 151 152
	/*
	 * Be backwards-compatible with previous kernels, so users
	 * won't get the wrong elevator.
	 */
153
	if (!strcmp(str, "as"))
154
		strcpy(chosen_elevator, "anticipatory");
155
	else
156
		strncpy(chosen_elevator, str, sizeof(chosen_elevator) - 1);
157
	return 1;
Linus Torvalds's avatar
Linus Torvalds committed
158 159 160 161
}

__setup("elevator=", elevator_setup);

162 163
static struct kobj_type elv_ktype;

164
static elevator_t *elevator_alloc(request_queue_t *q, struct elevator_type *e)
165
{
166 167 168
	elevator_t *eq;
	int i;

169
	eq = kmalloc_node(sizeof(elevator_t), GFP_KERNEL, q->node);
170 171 172 173 174 175 176 177 178 179 180
	if (unlikely(!eq))
		goto err;

	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);

181 182
	eq->hash = kmalloc_node(sizeof(struct hlist_head) * ELV_HASH_ENTRIES,
					GFP_KERNEL, q->node);
183 184 185 186 187 188
	if (!eq->hash)
		goto err;

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

189
	return eq;
190 191 192 193
err:
	kfree(eq);
	elevator_put(e);
	return NULL;
194 195 196 197 198
}

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

200
	elevator_put(e->elevator_type);
201
	kfree(e->hash);
202 203 204
	kfree(e);
}

Linus Torvalds's avatar
Linus Torvalds committed
205 206 207 208 209
int elevator_init(request_queue_t *q, char *name)
{
	struct elevator_type *e = NULL;
	struct elevator_queue *eq;
	int ret = 0;
Jens Axboe's avatar
Jens Axboe committed
210
	void *data;
Linus Torvalds's avatar
Linus Torvalds committed
211

212 213 214 215 216
	INIT_LIST_HEAD(&q->queue_head);
	q->last_merge = NULL;
	q->end_sector = 0;
	q->boundary_rq = NULL;

217
	if (name && !(e = elevator_get(name)))
Linus Torvalds's avatar
Linus Torvalds committed
218 219
		return -EINVAL;

220 221 222 223 224 225
	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");
226 227
	}

228
	eq = elevator_alloc(q, e);
229
	if (!eq)
Linus Torvalds's avatar
Linus Torvalds committed
230 231
		return -ENOMEM;

Jens Axboe's avatar
Jens Axboe committed
232 233
	data = elevator_init_queue(q, eq);
	if (!data) {
234
		kobject_put(&eq->kobj);
Jens Axboe's avatar
Jens Axboe committed
235 236
		return -ENOMEM;
	}
Linus Torvalds's avatar
Linus Torvalds committed
237

Jens Axboe's avatar
Jens Axboe committed
238
	elevator_attach(q, eq, data);
Linus Torvalds's avatar
Linus Torvalds committed
239 240 241
	return ret;
}

242 243
EXPORT_SYMBOL(elevator_init);

Linus Torvalds's avatar
Linus Torvalds committed
244 245
void elevator_exit(elevator_t *e)
{
246
	mutex_lock(&e->sysfs_lock);
Linus Torvalds's avatar
Linus Torvalds committed
247 248
	if (e->ops->elevator_exit_fn)
		e->ops->elevator_exit_fn(e);
249 250
	e->ops = NULL;
	mutex_unlock(&e->sysfs_lock);
Linus Torvalds's avatar
Linus Torvalds committed
251

252
	kobject_put(&e->kobj);
Linus Torvalds's avatar
Linus Torvalds committed
253 254
}

255 256
EXPORT_SYMBOL(elevator_exit);

257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303
static inline void __elv_rqhash_del(struct request *rq)
{
	hlist_del_init(&rq->hash);
}

static void elv_rqhash_del(request_queue_t *q, struct request *rq)
{
	if (ELV_ON_HASH(rq))
		__elv_rqhash_del(rq);
}

static void elv_rqhash_add(request_queue_t *q, struct request *rq)
{
	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))]);
}

static void elv_rqhash_reposition(request_queue_t *q, struct request *rq)
{
	__elv_rqhash_del(rq);
	elv_rqhash_add(q, rq);
}

static struct request *elv_rqhash_find(request_queue_t *q, sector_t offset)
{
	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;
}

304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362
/*
 * 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);

363 364
/*
 * Insert rq into dispatch queue of q.  Queue lock must be held on
365 366
 * entry.  rq is sort insted into the dispatch queue. To be used by
 * specific elevators.
367
 */
Jens Axboe's avatar
Jens Axboe committed
368
void elv_dispatch_sort(request_queue_t *q, struct request *rq)
369 370 371 372
{
	sector_t boundary;
	struct list_head *entry;

373 374
	if (q->last_merge == rq)
		q->last_merge = NULL;
375 376 377

	elv_rqhash_del(q, rq);

378
	q->nr_sorted--;
379

Jens Axboe's avatar
Jens Axboe committed
380
	boundary = q->end_sector;
381

382 383 384
	list_for_each_prev(entry, &q->queue_head) {
		struct request *pos = list_entry_rq(entry);

385
		if (pos->cmd_flags & (REQ_SOFTBARRIER|REQ_HARDBARRIER|REQ_STARTED))
386 387 388 389 390 391 392 393 394 395 396 397 398 399 400
			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);
}

401 402
EXPORT_SYMBOL(elv_dispatch_sort);

403
/*
404 405 406
 * 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.
407 408 409 410 411 412 413 414 415 416 417 418 419 420 421
 */
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);
}

422 423
EXPORT_SYMBOL(elv_dispatch_add_tail);

Linus Torvalds's avatar
Linus Torvalds committed
424 425 426
int elv_merge(request_queue_t *q, struct request **req, struct bio *bio)
{
	elevator_t *e = q->elevator;
427
	struct request *__rq;
428 429
	int ret;

430 431 432
	/*
	 * First try one-hit cache.
	 */
433 434 435 436 437 438 439
	if (q->last_merge) {
		ret = elv_try_merge(q->last_merge, bio);
		if (ret != ELEVATOR_NO_MERGE) {
			*req = q->last_merge;
			return ret;
		}
	}
Linus Torvalds's avatar
Linus Torvalds committed
440

441 442 443 444 445 446 447 448 449
	/*
	 * 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;
	}

Linus Torvalds's avatar
Linus Torvalds committed
450 451 452 453 454 455
	if (e->ops->elevator_merge_fn)
		return e->ops->elevator_merge_fn(q, req, bio);

	return ELEVATOR_NO_MERGE;
}

456
void elv_merged_request(request_queue_t *q, struct request *rq, int type)
Linus Torvalds's avatar
Linus Torvalds committed
457 458 459 460
{
	elevator_t *e = q->elevator;

	if (e->ops->elevator_merged_fn)
461
		e->ops->elevator_merged_fn(q, rq, type);
462

463 464
	if (type == ELEVATOR_BACK_MERGE)
		elv_rqhash_reposition(q, rq);
465

466
	q->last_merge = rq;
Linus Torvalds's avatar
Linus Torvalds committed
467 468 469 470 471 472 473 474 475
}

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);
476

477 478 479 480
	elv_rqhash_reposition(q, rq);
	elv_rqhash_del(q, next);

	q->nr_sorted--;
481
	q->last_merge = rq;
Linus Torvalds's avatar
Linus Torvalds committed
482 483
}

484
void elv_requeue_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
485 486 487 488 489 490 491
{
	elevator_t *e = q->elevator;

	/*
	 * it already went through dequeue, we need to decrement the
	 * in_flight count again
	 */
492
	if (blk_account_rq(rq)) {
Linus Torvalds's avatar
Linus Torvalds committed
493
		q->in_flight--;
494 495 496
		if (blk_sorted_rq(rq) && e->ops->elevator_deactivate_req_fn)
			e->ops->elevator_deactivate_req_fn(q, rq);
	}
Linus Torvalds's avatar
Linus Torvalds committed
497

498
	rq->cmd_flags &= ~REQ_STARTED;
Linus Torvalds's avatar
Linus Torvalds committed
499

500
	elv_insert(q, rq, ELEVATOR_INSERT_REQUEUE);
Linus Torvalds's avatar
Linus Torvalds committed
501 502
}

503 504 505 506 507 508 509 510 511 512 513 514 515 516
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);
	}
}

517
void elv_insert(request_queue_t *q, struct request *rq, int where)
Linus Torvalds's avatar
Linus Torvalds committed
518
{
519 520
	struct list_head *pos;
	unsigned ordseq;
521
	int unplug_it = 1;
522

523 524
	blk_add_trace_rq(q, rq, BLK_TA_INSERT);

Linus Torvalds's avatar
Linus Torvalds committed
525 526
	rq->q = q;

527 528
	switch (where) {
	case ELEVATOR_INSERT_FRONT:
529
		rq->cmd_flags |= REQ_SOFTBARRIER;
530 531 532 533 534

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

	case ELEVATOR_INSERT_BACK:
535
		rq->cmd_flags |= REQ_SOFTBARRIER;
536
		elv_drain_elevator(q);
537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553
		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));
554
		rq->cmd_flags |= REQ_SORTED;
555
		q->nr_sorted++;
556 557 558 559 560 561
		if (rq_mergeable(rq)) {
			elv_rqhash_add(q, rq);
			if (!q->last_merge)
				q->last_merge = rq;
		}

562 563 564 565 566 567
		/*
		 * 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);
568 569
		break;

570 571 572 573 574 575
	case ELEVATOR_INSERT_REQUEUE:
		/*
		 * If ordered flush isn't in progress, we do front
		 * insertion; otherwise, requests should be requeued
		 * in ordseq order.
		 */
576
		rq->cmd_flags |= REQ_SOFTBARRIER;
577 578 579 580 581 582 583 584 585 586 587 588 589 590 591

		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);
592 593 594 595 596
		/*
		 * most requeues happen because of a busy condition, don't
		 * force unplug of the queue for that case.
		 */
		unplug_it = 0;
597 598
		break;

599 600 601 602 603 604
	default:
		printk(KERN_ERR "%s: bad insertion point %d\n",
		       __FUNCTION__, where);
		BUG();
	}

605
	if (unplug_it && blk_queue_plugged(q)) {
606 607 608 609 610 611
		int nrq = q->rq.count[READ] + q->rq.count[WRITE]
			- q->in_flight;

		if (nrq >= q->unplug_thresh)
			__generic_unplug_device(q);
	}
Linus Torvalds's avatar
Linus Torvalds committed
612 613
}

614 615 616 617
void __elv_add_request(request_queue_t *q, struct request *rq, int where,
		       int plug)
{
	if (q->ordcolor)
618
		rq->cmd_flags |= REQ_ORDERED_COLOR;
619

620
	if (rq->cmd_flags & (REQ_SOFTBARRIER | REQ_HARDBARRIER)) {
621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640
		/*
		 * 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;
		}
641
	} else if (!(rq->cmd_flags & REQ_ELVPRIV) && where == ELEVATOR_INSERT_SORT)
642 643 644 645 646 647 648 649
		where = ELEVATOR_INSERT_BACK;

	if (plug)
		blk_plug_device(q);

	elv_insert(q, rq, where);
}

650 651
EXPORT_SYMBOL(__elv_add_request);

Linus Torvalds's avatar
Linus Torvalds committed
652 653 654 655 656 657 658 659 660 661
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);
}

662 663
EXPORT_SYMBOL(elv_add_request);

Linus Torvalds's avatar
Linus Torvalds committed
664 665
static inline struct request *__elv_next_request(request_queue_t *q)
{
666 667
	struct request *rq;

668 669 670 671 672 673
	while (1) {
		while (!list_empty(&q->queue_head)) {
			rq = list_entry_rq(q->queue_head.next);
			if (blk_do_ordered(q, &rq))
				return rq;
		}
Linus Torvalds's avatar
Linus Torvalds committed
674

675 676
		if (!q->elevator->ops->elevator_dispatch_fn(q, 0))
			return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
677 678 679 680 681 682 683 684 685
	}
}

struct request *elv_next_request(request_queue_t *q)
{
	struct request *rq;
	int ret;

	while ((rq = __elv_next_request(q)) != NULL) {
686
		if (!(rq->cmd_flags & REQ_STARTED)) {
687 688 689 690 691 692 693 694 695 696
			elevator_t *e = q->elevator;

			/*
			 * This is the first time the device driver
			 * sees this request (possibly after
			 * requeueing).  Notify IO scheduler.
			 */
			if (blk_sorted_rq(rq) &&
			    e->ops->elevator_activate_req_fn)
				e->ops->elevator_activate_req_fn(q, rq);
Linus Torvalds's avatar
Linus Torvalds committed
697

698 699 700 701 702
			/*
			 * 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
			 */
703
			rq->cmd_flags |= REQ_STARTED;
704
			blk_add_trace_rq(q, rq, BLK_TA_ISSUE);
705
		}
Linus Torvalds's avatar
Linus Torvalds committed
706

707
		if (!q->boundary_rq || q->boundary_rq == rq) {
Jens Axboe's avatar
Jens Axboe committed
708
			q->end_sector = rq_end_sector(rq);
709 710
			q->boundary_rq = NULL;
		}
Linus Torvalds's avatar
Linus Torvalds committed
711

712
		if ((rq->cmd_flags & REQ_DONTPREP) || !q->prep_rq_fn)
Linus Torvalds's avatar
Linus Torvalds committed
713 714 715 716 717 718
			break;

		ret = q->prep_rq_fn(q, rq);
		if (ret == BLKPREP_OK) {
			break;
		} else if (ret == BLKPREP_DEFER) {
719 720 721
			/*
			 * the request may have been (partially) prepped.
			 * we need to keep this request in the front to
722 723
			 * avoid resource deadlock.  REQ_STARTED will
			 * prevent other fs requests from passing this one.
724
			 */
Linus Torvalds's avatar
Linus Torvalds committed
725 726 727 728 729 730 731 732 733
			rq = NULL;
			break;
		} else if (ret == BLKPREP_KILL) {
			int nr_bytes = rq->hard_nr_sectors << 9;

			if (!nr_bytes)
				nr_bytes = rq->data_len;

			blkdev_dequeue_request(rq);
734
			rq->cmd_flags |= REQ_QUIET;
Linus Torvalds's avatar
Linus Torvalds committed
735
			end_that_request_chunk(rq, 0, nr_bytes);
736
			end_that_request_last(rq, 0);
Linus Torvalds's avatar
Linus Torvalds committed
737 738 739 740 741 742 743 744 745 746
		} else {
			printk(KERN_ERR "%s: bad return=%d\n", __FUNCTION__,
								ret);
			break;
		}
	}

	return rq;
}

747 748
EXPORT_SYMBOL(elv_next_request);

749
void elv_dequeue_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
750
{
751
	BUG_ON(list_empty(&rq->queuelist));
752
	BUG_ON(ELV_ON_HASH(rq));
753 754

	list_del_init(&rq->queuelist);
Linus Torvalds's avatar
Linus Torvalds committed
755 756 757 758

	/*
	 * 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
759
	 * the driver side.
Linus Torvalds's avatar
Linus Torvalds committed
760 761 762 763 764
	 */
	if (blk_account_rq(rq))
		q->in_flight++;
}

765 766
EXPORT_SYMBOL(elv_dequeue_request);

Linus Torvalds's avatar
Linus Torvalds committed
767 768 769 770
int elv_queue_empty(request_queue_t *q)
{
	elevator_t *e = q->elevator;

771 772 773
	if (!list_empty(&q->queue_head))
		return 0;

Linus Torvalds's avatar
Linus Torvalds committed
774 775 776
	if (e->ops->elevator_queue_empty_fn)
		return e->ops->elevator_queue_empty_fn(q);

777
	return 1;
Linus Torvalds's avatar
Linus Torvalds committed
778 779
}

780 781
EXPORT_SYMBOL(elv_queue_empty);

Linus Torvalds's avatar
Linus Torvalds committed
782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799
struct request *elv_latter_request(request_queue_t *q, struct request *rq)
{
	elevator_t *e = q->elevator;

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

struct request *elv_former_request(request_queue_t *q, struct request *rq)
{
	elevator_t *e = q->elevator;

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

800
int elv_set_request(request_queue_t *q, struct request *rq, gfp_t gfp_mask)
Linus Torvalds's avatar
Linus Torvalds committed
801 802 803 804
{
	elevator_t *e = q->elevator;

	if (e->ops->elevator_set_req_fn)
805
		return e->ops->elevator_set_req_fn(q, rq, gfp_mask);
Linus Torvalds's avatar
Linus Torvalds committed
806 807 808 809 810 811 812 813 814 815 816 817 818

	rq->elevator_private = NULL;
	return 0;
}

void elv_put_request(request_queue_t *q, struct request *rq)
{
	elevator_t *e = q->elevator;

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

819
int elv_may_queue(request_queue_t *q, int rw)
Linus Torvalds's avatar
Linus Torvalds committed
820 821 822 823
{
	elevator_t *e = q->elevator;

	if (e->ops->elevator_may_queue_fn)
824
		return e->ops->elevator_may_queue_fn(q, rw);
Linus Torvalds's avatar
Linus Torvalds committed
825 826 827 828 829 830 831 832 833 834 835

	return ELV_MQUEUE_MAY;
}

void elv_completed_request(request_queue_t *q, struct request *rq)
{
	elevator_t *e = q->elevator;

	/*
	 * request is released from the driver, io must be done
	 */
836
	if (blk_account_rq(rq)) {
Linus Torvalds's avatar
Linus Torvalds committed
837
		q->in_flight--;
838 839 840
		if (blk_sorted_rq(rq) && e->ops->elevator_completed_req_fn)
			e->ops->elevator_completed_req_fn(q, rq);
	}
841

842 843 844 845 846 847 848
	/*
	 * 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 &&
849 850 851 852 853
		    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);
		}
854
	}
Linus Torvalds's avatar
Linus Torvalds committed
855 856
}

857 858 859 860
#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)
Linus Torvalds's avatar
Linus Torvalds committed
861
{
862 863 864 865 866 867 868 869 870 871 872 873
	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;
}
Linus Torvalds's avatar
Linus Torvalds committed
874

875 876 877 878 879 880 881
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;
Linus Torvalds's avatar
Linus Torvalds committed
882

883 884
	if (!entry->store)
		return -EIO;
Linus Torvalds's avatar
Linus Torvalds committed
885

886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910
	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;

	e->kobj.parent = &q->kobj;

	error = kobject_add(&e->kobj);
	if (!error) {
911
		struct elv_fs_entry *attr = e->elevator_type->elevator_attrs;
912
		if (attr) {
913 914
			while (attr->attr.name) {
				if (sysfs_create_file(&e->kobj, &attr->attr))
915
					break;
916
				attr++;
917 918 919 920 921
			}
		}
		kobject_uevent(&e->kobj, KOBJ_ADD);
	}
	return error;
Linus Torvalds's avatar
Linus Torvalds committed
922 923
}

Jens Axboe's avatar
Jens Axboe committed
924 925 926 927 928 929
static void __elv_unregister_queue(elevator_t *e)
{
	kobject_uevent(&e->kobj, KOBJ_REMOVE);
	kobject_del(&e->kobj);
}

Linus Torvalds's avatar
Linus Torvalds committed
930 931
void elv_unregister_queue(struct request_queue *q)
{
Jens Axboe's avatar
Jens Axboe committed
932 933
	if (q)
		__elv_unregister_queue(q->elevator);
Linus Torvalds's avatar
Linus Torvalds committed
934 935 936 937
}

int elv_register(struct elevator_type *e)
{
938
	spin_lock_irq(&elv_list_lock);
939
	BUG_ON(elevator_find(e->elevator_name));
Linus Torvalds's avatar
Linus Torvalds committed
940 941 942 943
	list_add_tail(&e->list, &elv_list);
	spin_unlock_irq(&elv_list_lock);

	printk(KERN_INFO "io scheduler %s registered", e->elevator_name);
944 945 946 947
	if (!strcmp(e->elevator_name, chosen_elevator) ||
			(!*chosen_elevator &&
			 !strcmp(e->elevator_name, CONFIG_DEFAULT_IOSCHED)))
				printk(" (default)");
Linus Torvalds's avatar
Linus Torvalds committed
948 949 950 951 952 953 954
	printk("\n");
	return 0;
}
EXPORT_SYMBOL_GPL(elv_register);

void elv_unregister(struct elevator_type *e)
{
955 956 957 958 959
	struct task_struct *g, *p;

	/*
	 * Iterate every thread in the process to remove the io contexts.
	 */
960 961 962 963
	if (e->ops.trim) {
		read_lock(&tasklist_lock);
		do_each_thread(g, p) {
			task_lock(p);
964 965
			if (p->io_context)
				e->ops.trim(p->io_context);
966 967 968 969
			task_unlock(p);
		} while_each_thread(g, p);
		read_unlock(&tasklist_lock);
	}
970

Linus Torvalds's avatar
Linus Torvalds committed
971 972 973 974 975 976 977 978 979 980
	spin_lock_irq(&elv_list_lock);
	list_del_init(&e->list);
	spin_unlock_irq(&elv_list_lock);
}
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
981
 * one, if the new one fails init for some reason.
Linus Torvalds's avatar
Linus Torvalds committed
982
 */
983
static int elevator_switch(request_queue_t *q, struct elevator_type *new_e)
Linus Torvalds's avatar
Linus Torvalds committed
984
{
985
	elevator_t *old_elevator, *e;
Jens Axboe's avatar
Jens Axboe committed
986
	void *data;
Linus Torvalds's avatar
Linus Torvalds committed
987

988 989 990
	/*
	 * Allocate new elevator
	 */
991
	e = elevator_alloc(q, new_e);
Linus Torvalds's avatar
Linus Torvalds committed
992
	if (!e)
993
		return 0;
Linus Torvalds's avatar
Linus Torvalds committed
994

Jens Axboe's avatar
Jens Axboe committed
995 996 997 998 999 1000
	data = elevator_init_queue(q, e);
	if (!data) {
		kobject_put(&e->kobj);
		return 0;
	}

Linus Torvalds's avatar
Linus Torvalds committed
1001
	/*
1002
	 * Turn on BYPASS and drain all requests w/ elevator private data
Linus Torvalds's avatar
Linus Torvalds committed
1003
	 */
1004 1005
	spin_lock_irq(q->queue_lock);

1006
	set_bit(QUEUE_FLAG_ELVSWITCH, &q->queue_flags);
1007

1008
	elv_drain_elevator(q);
1009 1010

	while (q->rq.elvpriv) {
1011 1012
		blk_remove_plug(q);
		q->request_fn(q);
1013
		spin_unlock_irq(q->queue_lock);
1014
		msleep(10);
1015
		spin_lock_irq(q->queue_lock);
1016
		elv_drain_elevator(q);
1017 1018
	}

Linus Torvalds's avatar
Linus Torvalds committed
1019
	/*
Jens Axboe's avatar
Jens Axboe committed
1020
	 * Remember old elevator.
Linus Torvalds's avatar
Linus Torvalds committed
1021 1022 1023 1024 1025 1026
	 */
	old_elevator = q->elevator;

	/*
	 * attach and start new elevator
	 */
Jens Axboe's avatar
Jens Axboe committed
1027 1028 1029 1030 1031
	elevator_attach(q, e, data);

	spin_unlock_irq(q->queue_lock);

	__elv_unregister_queue(old_elevator);
Linus Torvalds's avatar
Linus Torvalds committed
1032 1033 1034 1035 1036

	if (elv_register_queue(q))
		goto fail_register;

	/*
1037
	 * finally exit old elevator and turn off BYPASS.
Linus Torvalds's avatar
Linus Torvalds committed
1038 1039
	 */
	elevator_exit(old_elevator);
1040
	clear_bit(QUEUE_FLAG_ELVSWITCH, &q->queue_flags);
1041
	return 1;
Linus Torvalds's avatar
Linus Torvalds committed
1042 1043 1044 1045 1046 1047 1048 1049 1050

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);
1051
	clear_bit(QUEUE_FLAG_ELVSWITCH, &q->queue_flags);
1052
	return 0;
Linus Torvalds's avatar
Linus Torvalds committed
1053 1054 1055 1056 1057
}

ssize_t elv_iosched_store(request_queue_t *q, const char *name, size_t count)
{
	char elevator_name[ELV_NAME_MAX];
1058
	size_t len;
Linus Torvalds's avatar
Linus Torvalds committed
1059 1060
	struct elevator_type *e;

1061 1062 1063
	elevator_name[sizeof(elevator_name) - 1] = '\0';
	strncpy(elevator_name, name, sizeof(elevator_name) - 1);
	len = strlen(elevator_name);
Linus Torvalds's avatar
Linus Torvalds committed
1064

1065 1066
	if (len && elevator_name[len - 1] == '\n')
		elevator_name[len - 1] = '\0';
Linus Torvalds's avatar
Linus Torvalds committed
1067 1068 1069 1070 1071 1072 1073

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

1074 1075
	if (!strcmp(elevator_name, q->elevator->elevator_type->elevator_name)) {
		elevator_put(e);
Linus Torvalds's avatar
Linus Torvalds committed
1076
		return count;
1077
	}
Linus Torvalds's avatar
Linus Torvalds committed
1078

1079 1080
	if (!elevator_switch(q, e))
		printk(KERN_ERR "elevator: switch to %s failed\n",elevator_name);
Linus Torvalds's avatar
Linus Torvalds committed
1081 1082 1083 1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 1096 1097 1098 1099 1100 1101 1102 1103 1104 1105 1106
	return count;
}

ssize_t elv_iosched_show(request_queue_t *q, char *name)
{
	elevator_t *e = q->elevator;
	struct elevator_type *elv = e->elevator_type;
	struct list_head *entry;
	int len = 0;

	spin_lock_irq(q->queue_lock);
	list_for_each(entry, &elv_list) {
		struct elevator_type *__e;

		__e = list_entry(entry, struct elevator_type, list);
		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);
	}
	spin_unlock_irq(q->queue_lock);

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

1107 1108 1109 1110 1111 1112 1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 1126 1127 1128 1129
struct request *elv_rb_former_request(request_queue_t *q, struct request *rq)
{
	struct rb_node *rbprev = rb_prev(&rq->rb_node);

	if (rbprev)
		return rb_entry_rq(rbprev);

	return NULL;
}

EXPORT_SYMBOL(elv_rb_former_request);

struct request *elv_rb_latter_request(request_queue_t *q, struct request *rq)
{
	struct rb_node *rbnext = rb_next(&rq->rb_node);

	if (rbnext)
		return rb_entry_rq(rbnext);

	return NULL;
}

EXPORT_SYMBOL(elv_rb_latter_request);