deadline-iosched.c 18.6 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
/*
 *  Deadline i/o scheduler.
 *
 *  Copyright (C) 2002 Jens Axboe <axboe@suse.de>
 */
#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>
#include <linux/hash.h>
#include <linux/rbtree.h>

/*
 * See Documentation/block/deadline-iosched.txt
 */
21 22 23 24
static const int read_expire = HZ / 2;  /* max time before a read is submitted. */
static const int write_expire = 5 * HZ; /* ditto for writes, these limits are SOFT! */
static const int writes_starved = 2;    /* max times reads can starve a write */
static const int fifo_batch = 16;       /* # of sequential requests treated as one
Linus Torvalds's avatar
Linus Torvalds committed
25 26 27 28 29 30 31
				     by the above parameters. For throughput. */

static const int deadline_hash_shift = 5;
#define DL_HASH_BLOCK(sec)	((sec) >> 3)
#define DL_HASH_FN(sec)		(hash_long(DL_HASH_BLOCK((sec)), deadline_hash_shift))
#define DL_HASH_ENTRIES		(1 << deadline_hash_shift)
#define rq_hash_key(rq)		((rq)->sector + (rq)->nr_sectors)
32
#define ON_HASH(drq)		(!hlist_unhashed(&(drq)->hash))
Linus Torvalds's avatar
Linus Torvalds committed
33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48

struct deadline_data {
	/*
	 * run time data
	 */

	/*
	 * requests (deadline_rq s) are present on both sort_list and fifo_list
	 */
	struct rb_root sort_list[2];	
	struct list_head fifo_list[2];
	
	/*
	 * next in sort order. read, write or both are NULL
	 */
	struct deadline_rq *next_drq[2];
49
	struct hlist_head *hash;	/* request hash */
Linus Torvalds's avatar
Linus Torvalds committed
50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79
	unsigned int batching;		/* number of sequential requests made */
	sector_t last_sector;		/* head position */
	unsigned int starved;		/* times reads have starved writes */

	/*
	 * settings that change how the i/o scheduler behaves
	 */
	int fifo_expire[2];
	int fifo_batch;
	int writes_starved;
	int front_merges;

	mempool_t *drq_pool;
};

/*
 * pre-request data.
 */
struct deadline_rq {
	/*
	 * rbtree index, key is the starting offset
	 */
	struct rb_node rb_node;
	sector_t rb_key;

	struct request *request;

	/*
	 * request hash, key is the ending offset (for back merge lookup)
	 */
80
	struct hlist_node hash;
Linus Torvalds's avatar
Linus Torvalds committed
81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99

	/*
	 * expire fifo
	 */
	struct list_head fifo;
	unsigned long expires;
};

static void deadline_move_request(struct deadline_data *dd, struct deadline_rq *drq);

static kmem_cache_t *drq_pool;

#define RQ_DATA(rq)	((struct deadline_rq *) (rq)->elevator_private)

/*
 * the back merge hash support functions
 */
static inline void __deadline_del_drq_hash(struct deadline_rq *drq)
{
100
	hlist_del_init(&drq->hash);
Linus Torvalds's avatar
Linus Torvalds committed
101 102 103 104 105 106 107 108 109 110 111 112 113 114 115
}

static inline void deadline_del_drq_hash(struct deadline_rq *drq)
{
	if (ON_HASH(drq))
		__deadline_del_drq_hash(drq);
}

static inline void
deadline_add_drq_hash(struct deadline_data *dd, struct deadline_rq *drq)
{
	struct request *rq = drq->request;

	BUG_ON(ON_HASH(drq));

116
	hlist_add_head(&drq->hash, &dd->hash[DL_HASH_FN(rq_hash_key(rq))]);
Linus Torvalds's avatar
Linus Torvalds committed
117 118 119 120 121 122 123 124 125
}

/*
 * move hot entry to front of chain
 */
static inline void
deadline_hot_drq_hash(struct deadline_data *dd, struct deadline_rq *drq)
{
	struct request *rq = drq->request;
126
	struct hlist_head *head = &dd->hash[DL_HASH_FN(rq_hash_key(rq))];
Linus Torvalds's avatar
Linus Torvalds committed
127

128 129 130
	if (ON_HASH(drq) && &drq->hash != head->first) {
		hlist_del(&drq->hash);
		hlist_add_head(&drq->hash, head);
Linus Torvalds's avatar
Linus Torvalds committed
131 132 133 134 135 136
	}
}

static struct request *
deadline_find_drq_hash(struct deadline_data *dd, sector_t offset)
{
137 138 139
	struct hlist_head *hash_list = &dd->hash[DL_HASH_FN(offset)];
	struct hlist_node *entry, *next;
	struct deadline_rq *drq;
Linus Torvalds's avatar
Linus Torvalds committed
140

141
	hlist_for_each_entry_safe(drq, entry, next, hash_list, hash) {
Linus Torvalds's avatar
Linus Torvalds committed
142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218
		struct request *__rq = drq->request;

		BUG_ON(!ON_HASH(drq));

		if (!rq_mergeable(__rq)) {
			__deadline_del_drq_hash(drq);
			continue;
		}

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

	return NULL;
}

/*
 * rb tree support functions
 */
#define rb_entry_drq(node)	rb_entry((node), struct deadline_rq, rb_node)
#define DRQ_RB_ROOT(dd, drq)	(&(dd)->sort_list[rq_data_dir((drq)->request)])
#define rq_rb_key(rq)		(rq)->sector

static struct deadline_rq *
__deadline_add_drq_rb(struct deadline_data *dd, struct deadline_rq *drq)
{
	struct rb_node **p = &DRQ_RB_ROOT(dd, drq)->rb_node;
	struct rb_node *parent = NULL;
	struct deadline_rq *__drq;

	while (*p) {
		parent = *p;
		__drq = rb_entry_drq(parent);

		if (drq->rb_key < __drq->rb_key)
			p = &(*p)->rb_left;
		else if (drq->rb_key > __drq->rb_key)
			p = &(*p)->rb_right;
		else
			return __drq;
	}

	rb_link_node(&drq->rb_node, parent, p);
	return NULL;
}

static void
deadline_add_drq_rb(struct deadline_data *dd, struct deadline_rq *drq)
{
	struct deadline_rq *__alias;

	drq->rb_key = rq_rb_key(drq->request);

retry:
	__alias = __deadline_add_drq_rb(dd, drq);
	if (!__alias) {
		rb_insert_color(&drq->rb_node, DRQ_RB_ROOT(dd, drq));
		return;
	}

	deadline_move_request(dd, __alias);
	goto retry;
}

static inline void
deadline_del_drq_rb(struct deadline_data *dd, struct deadline_rq *drq)
{
	const int data_dir = rq_data_dir(drq->request);

	if (dd->next_drq[data_dir] == drq) {
		struct rb_node *rbnext = rb_next(&drq->rb_node);

		dd->next_drq[data_dir] = NULL;
		if (rbnext)
			dd->next_drq[data_dir] = rb_entry_drq(rbnext);
	}

219
	BUG_ON(!RB_EMPTY_NODE(&drq->rb_node));
220
	rb_erase(&drq->rb_node, DRQ_RB_ROOT(dd, drq));
221
	RB_CLEAR_NODE(&drq->rb_node);
Linus Torvalds's avatar
Linus Torvalds committed
222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264
}

static struct request *
deadline_find_drq_rb(struct deadline_data *dd, sector_t sector, int data_dir)
{
	struct rb_node *n = dd->sort_list[data_dir].rb_node;
	struct deadline_rq *drq;

	while (n) {
		drq = rb_entry_drq(n);

		if (sector < drq->rb_key)
			n = n->rb_left;
		else if (sector > drq->rb_key)
			n = n->rb_right;
		else
			return drq->request;
	}

	return NULL;
}

/*
 * deadline_find_first_drq finds the first (lowest sector numbered) request
 * for the specified data_dir. Used to sweep back to the start of the disk
 * (1-way elevator) after we process the last (highest sector) request.
 */
static struct deadline_rq *
deadline_find_first_drq(struct deadline_data *dd, int data_dir)
{
	struct rb_node *n = dd->sort_list[data_dir].rb_node;

	for (;;) {
		if (n->rb_left == NULL)
			return rb_entry_drq(n);
		
		n = n->rb_left;
	}
}

/*
 * add drq to rbtree and fifo
 */
265
static void
Linus Torvalds's avatar
Linus Torvalds committed
266 267 268 269 270 271 272 273 274 275 276 277 278 279
deadline_add_request(struct request_queue *q, struct request *rq)
{
	struct deadline_data *dd = q->elevator->elevator_data;
	struct deadline_rq *drq = RQ_DATA(rq);

	const int data_dir = rq_data_dir(drq->request);

	deadline_add_drq_rb(dd, drq);
	/*
	 * set expire time (only used for reads) and add to fifo list
	 */
	drq->expires = jiffies + dd->fifo_expire[data_dir];
	list_add_tail(&drq->fifo, &dd->fifo_list[data_dir]);

280
	if (rq_mergeable(rq))
Linus Torvalds's avatar
Linus Torvalds committed
281 282 283 284 285 286 287 288 289
		deadline_add_drq_hash(dd, drq);
}

/*
 * remove rq from rbtree, fifo, and hash
 */
static void deadline_remove_request(request_queue_t *q, struct request *rq)
{
	struct deadline_rq *drq = RQ_DATA(rq);
290
	struct deadline_data *dd = q->elevator->elevator_data;
Linus Torvalds's avatar
Linus Torvalds committed
291

292 293
	list_del_init(&drq->fifo);
	deadline_del_drq_rb(dd, drq);
294
	deadline_del_drq_hash(drq);
Linus Torvalds's avatar
Linus Torvalds committed
295 296 297 298 299 300 301 302 303 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 363 364 365 366 367 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
}

static int
deadline_merge(request_queue_t *q, struct request **req, struct bio *bio)
{
	struct deadline_data *dd = q->elevator->elevator_data;
	struct request *__rq;
	int ret;

	/*
	 * see if the merge hash can satisfy a back merge
	 */
	__rq = deadline_find_drq_hash(dd, bio->bi_sector);
	if (__rq) {
		BUG_ON(__rq->sector + __rq->nr_sectors != bio->bi_sector);

		if (elv_rq_merge_ok(__rq, bio)) {
			ret = ELEVATOR_BACK_MERGE;
			goto out;
		}
	}

	/*
	 * check for front merge
	 */
	if (dd->front_merges) {
		sector_t rb_key = bio->bi_sector + bio_sectors(bio);

		__rq = deadline_find_drq_rb(dd, rb_key, bio_data_dir(bio));
		if (__rq) {
			BUG_ON(rb_key != rq_rb_key(__rq));

			if (elv_rq_merge_ok(__rq, bio)) {
				ret = ELEVATOR_FRONT_MERGE;
				goto out;
			}
		}
	}

	return ELEVATOR_NO_MERGE;
out:
	if (ret)
		deadline_hot_drq_hash(dd, RQ_DATA(__rq));
	*req = __rq;
	return ret;
}

static void deadline_merged_request(request_queue_t *q, struct request *req)
{
	struct deadline_data *dd = q->elevator->elevator_data;
	struct deadline_rq *drq = RQ_DATA(req);

	/*
	 * hash always needs to be repositioned, key is end sector
	 */
	deadline_del_drq_hash(drq);
	deadline_add_drq_hash(dd, drq);

	/*
	 * if the merge was a front merge, we need to reposition request
	 */
	if (rq_rb_key(req) != drq->rb_key) {
		deadline_del_drq_rb(dd, drq);
		deadline_add_drq_rb(dd, drq);
	}
}

static void
deadline_merged_requests(request_queue_t *q, struct request *req,
			 struct request *next)
{
	struct deadline_data *dd = q->elevator->elevator_data;
	struct deadline_rq *drq = RQ_DATA(req);
	struct deadline_rq *dnext = RQ_DATA(next);

	BUG_ON(!drq);
	BUG_ON(!dnext);

	/*
	 * reposition drq (this is the merged request) in hash, and in rbtree
	 * in case of a front merge
	 */
	deadline_del_drq_hash(drq);
	deadline_add_drq_hash(dd, drq);

	if (rq_rb_key(req) != drq->rb_key) {
		deadline_del_drq_rb(dd, drq);
		deadline_add_drq_rb(dd, drq);
	}

	/*
	 * if dnext expires before drq, assign its expire time to drq
	 * and move into dnext position (dnext will be deleted) in fifo
	 */
	if (!list_empty(&drq->fifo) && !list_empty(&dnext->fifo)) {
		if (time_before(dnext->expires, drq->expires)) {
			list_move(&drq->fifo, &dnext->fifo);
			drq->expires = dnext->expires;
		}
	}

	/*
	 * kill knowledge of next, this one is a goner
	 */
	deadline_remove_request(q, next);
}

/*
 * move request from sort list to dispatch queue.
 */
static inline void
deadline_move_to_dispatch(struct deadline_data *dd, struct deadline_rq *drq)
{
	request_queue_t *q = drq->request->q;

	deadline_remove_request(q, drq->request);
411
	elv_dispatch_add_tail(q, drq->request);
Linus Torvalds's avatar
Linus Torvalds committed
412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460
}

/*
 * move an entry to dispatch queue
 */
static void
deadline_move_request(struct deadline_data *dd, struct deadline_rq *drq)
{
	const int data_dir = rq_data_dir(drq->request);
	struct rb_node *rbnext = rb_next(&drq->rb_node);

	dd->next_drq[READ] = NULL;
	dd->next_drq[WRITE] = NULL;

	if (rbnext)
		dd->next_drq[data_dir] = rb_entry_drq(rbnext);
	
	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
 */
461
static int deadline_dispatch_requests(request_queue_t *q, int force)
Linus Torvalds's avatar
Linus Torvalds committed
462
{
463
	struct deadline_data *dd = q->elevator->elevator_data;
Linus Torvalds's avatar
Linus Torvalds committed
464 465 466
	const int reads = !list_empty(&dd->fifo_list[READ]);
	const int writes = !list_empty(&dd->fifo_list[WRITE]);
	struct deadline_rq *drq;
467
	int data_dir;
Linus Torvalds's avatar
Linus Torvalds committed
468 469 470 471

	/*
	 * batches are currently reads XOR writes
	 */
472 473 474 475
	if (dd->next_drq[WRITE])
		drq = dd->next_drq[WRITE];
	else
		drq = dd->next_drq[READ];
Linus Torvalds's avatar
Linus Torvalds committed
476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494

	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) {
495
		BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[READ]));
Linus Torvalds's avatar
Linus Torvalds committed
496 497 498 499 500 501 502 503 504 505 506 507 508 509 510

		if (writes && (dd->starved++ >= dd->writes_starved))
			goto dispatch_writes;

		data_dir = READ;

		goto dispatch_find_request;
	}

	/*
	 * there are either no reads or writes have been starved
	 */

	if (writes) {
dispatch_writes:
511
		BUG_ON(RB_EMPTY_ROOT(&dd->sort_list[WRITE]));
Linus Torvalds's avatar
Linus Torvalds committed
512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560

		dd->starved = 0;

		data_dir = WRITE;

		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 int deadline_queue_empty(request_queue_t *q)
{
	struct deadline_data *dd = q->elevator->elevator_data;

561 562
	return list_empty(&dd->fifo_list[WRITE])
		&& list_empty(&dd->fifo_list[READ]);
Linus Torvalds's avatar
Linus Torvalds committed
563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604
}

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_queue(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
 */
Jens Axboe's avatar
Jens Axboe committed
605
static void *deadline_init_queue(request_queue_t *q, elevator_t *e)
Linus Torvalds's avatar
Linus Torvalds committed
606 607 608 609 610
{
	struct deadline_data *dd;
	int i;

	if (!drq_pool)
Jens Axboe's avatar
Jens Axboe committed
611
		return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
612

613
	dd = kmalloc_node(sizeof(*dd), GFP_KERNEL, q->node);
Linus Torvalds's avatar
Linus Torvalds committed
614
	if (!dd)
Jens Axboe's avatar
Jens Axboe committed
615
		return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
616 617
	memset(dd, 0, sizeof(*dd));

618
	dd->hash = kmalloc_node(sizeof(struct hlist_head)*DL_HASH_ENTRIES,
619
				GFP_KERNEL, q->node);
Linus Torvalds's avatar
Linus Torvalds committed
620 621
	if (!dd->hash) {
		kfree(dd);
Jens Axboe's avatar
Jens Axboe committed
622
		return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
623 624
	}

625 626
	dd->drq_pool = mempool_create_node(BLKDEV_MIN_RQ, mempool_alloc_slab,
					mempool_free_slab, drq_pool, q->node);
Linus Torvalds's avatar
Linus Torvalds committed
627 628 629
	if (!dd->drq_pool) {
		kfree(dd->hash);
		kfree(dd);
Jens Axboe's avatar
Jens Axboe committed
630
		return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
631 632 633
	}

	for (i = 0; i < DL_HASH_ENTRIES; i++)
634
		INIT_HLIST_HEAD(&dd->hash[i]);
Linus Torvalds's avatar
Linus Torvalds committed
635 636 637 638 639 640 641 642 643 644

	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->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;
Jens Axboe's avatar
Jens Axboe committed
645
	return dd;
Linus Torvalds's avatar
Linus Torvalds committed
646 647 648 649 650 651 652
}

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

653 654
	mempool_free(drq, dd->drq_pool);
	rq->elevator_private = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
655 656 657
}

static int
658
deadline_set_request(request_queue_t *q, struct request *rq, struct bio *bio,
Al Viro's avatar
Al Viro committed
659
		     gfp_t gfp_mask)
Linus Torvalds's avatar
Linus Torvalds committed
660 661 662 663 664 665 666
{
	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));
667
		RB_CLEAR_NODE(&drq->rb_node);
Linus Torvalds's avatar
Linus Torvalds committed
668 669
		drq->request = rq;

670
		INIT_HLIST_NODE(&drq->hash);
Linus Torvalds's avatar
Linus Torvalds committed
671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700

		INIT_LIST_HEAD(&drq->fifo);

		rq->elevator_private = drq;
		return 0;
	}

	return 1;
}

/*
 * sysfs parts below
 */

static ssize_t
deadline_var_show(int var, char *page)
{
	return sprintf(page, "%d\n", var);
}

static ssize_t
deadline_var_store(int *var, const char *page, size_t count)
{
	char *p = (char *) page;

	*var = simple_strtol(p, &p, 10);
	return count;
}

#define SHOW_FUNCTION(__FUNC, __VAR, __CONV)				\
701
static ssize_t __FUNC(elevator_t *e, char *page)			\
Linus Torvalds's avatar
Linus Torvalds committed
702
{									\
703 704
	struct deadline_data *dd = e->elevator_data;			\
	int __data = __VAR;						\
Linus Torvalds's avatar
Linus Torvalds committed
705 706 707 708
	if (__CONV)							\
		__data = jiffies_to_msecs(__data);			\
	return deadline_var_show(__data, (page));			\
}
709 710 711 712 713
SHOW_FUNCTION(deadline_read_expire_show, dd->fifo_expire[READ], 1);
SHOW_FUNCTION(deadline_write_expire_show, dd->fifo_expire[WRITE], 1);
SHOW_FUNCTION(deadline_writes_starved_show, dd->writes_starved, 0);
SHOW_FUNCTION(deadline_front_merges_show, dd->front_merges, 0);
SHOW_FUNCTION(deadline_fifo_batch_show, dd->fifo_batch, 0);
Linus Torvalds's avatar
Linus Torvalds committed
714 715 716
#undef SHOW_FUNCTION

#define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV)			\
717
static ssize_t __FUNC(elevator_t *e, const char *page, size_t count)	\
Linus Torvalds's avatar
Linus Torvalds committed
718
{									\
719
	struct deadline_data *dd = e->elevator_data;			\
Linus Torvalds's avatar
Linus Torvalds committed
720 721 722 723 724 725 726 727 728 729 730 731
	int __data;							\
	int ret = deadline_var_store(&__data, (page), count);		\
	if (__data < (MIN))						\
		__data = (MIN);						\
	else if (__data > (MAX))					\
		__data = (MAX);						\
	if (__CONV)							\
		*(__PTR) = msecs_to_jiffies(__data);			\
	else								\
		*(__PTR) = __data;					\
	return ret;							\
}
732 733 734 735 736
STORE_FUNCTION(deadline_read_expire_store, &dd->fifo_expire[READ], 0, INT_MAX, 1);
STORE_FUNCTION(deadline_write_expire_store, &dd->fifo_expire[WRITE], 0, INT_MAX, 1);
STORE_FUNCTION(deadline_writes_starved_store, &dd->writes_starved, INT_MIN, INT_MAX, 0);
STORE_FUNCTION(deadline_front_merges_store, &dd->front_merges, 0, 1, 0);
STORE_FUNCTION(deadline_fifo_batch_store, &dd->fifo_batch, 0, INT_MAX, 0);
Linus Torvalds's avatar
Linus Torvalds committed
737 738
#undef STORE_FUNCTION

739 740 741 742 743 744 745 746 747 748 749
#define DD_ATTR(name) \
	__ATTR(name, S_IRUGO|S_IWUSR, deadline_##name##_show, \
				      deadline_##name##_store)

static struct elv_fs_entry deadline_attrs[] = {
	DD_ATTR(read_expire),
	DD_ATTR(write_expire),
	DD_ATTR(writes_starved),
	DD_ATTR(front_merges),
	DD_ATTR(fifo_batch),
	__ATTR_NULL
Linus Torvalds's avatar
Linus Torvalds committed
750 751 752 753 754 755 756
};

static struct elevator_type iosched_deadline = {
	.ops = {
		.elevator_merge_fn = 		deadline_merge,
		.elevator_merged_fn =		deadline_merged_request,
		.elevator_merge_req_fn =	deadline_merged_requests,
757 758
		.elevator_dispatch_fn =		deadline_dispatch_requests,
		.elevator_add_req_fn =		deadline_add_request,
Linus Torvalds's avatar
Linus Torvalds committed
759 760 761 762 763 764 765 766 767
		.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_queue,
		.elevator_exit_fn =		deadline_exit_queue,
	},

768
	.elevator_attrs = deadline_attrs,
Linus Torvalds's avatar
Linus Torvalds committed
769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801
	.elevator_name = "deadline",
	.elevator_owner = THIS_MODULE,
};

static int __init deadline_init(void)
{
	int ret;

	drq_pool = kmem_cache_create("deadline_drq", sizeof(struct deadline_rq),
				     0, 0, NULL, NULL);

	if (!drq_pool)
		return -ENOMEM;

	ret = elv_register(&iosched_deadline);
	if (ret)
		kmem_cache_destroy(drq_pool);

	return ret;
}

static void __exit deadline_exit(void)
{
	kmem_cache_destroy(drq_pool);
	elv_unregister(&iosched_deadline);
}

module_init(deadline_init);
module_exit(deadline_exit);

MODULE_AUTHOR("Jens Axboe");
MODULE_LICENSE("GPL");
MODULE_DESCRIPTION("deadline IO scheduler");