cfq-iosched.c 51.2 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6
/*
 *  CFQ, or complete fairness queueing, disk scheduler.
 *
 *  Based on ideas from a previously unfinished io
 *  scheduler (round robin per-process disk scheduling) and Andrea Arcangeli.
 *
7
 *  Copyright (C) 2003 Jens Axboe <axboe@kernel.dk>
Linus Torvalds's avatar
Linus Torvalds committed
8 9
 */
#include <linux/module.h>
Al Viro's avatar
Al Viro committed
10 11
#include <linux/blkdev.h>
#include <linux/elevator.h>
Linus Torvalds's avatar
Linus Torvalds committed
12 13
#include <linux/hash.h>
#include <linux/rbtree.h>
14
#include <linux/ioprio.h>
Linus Torvalds's avatar
Linus Torvalds committed
15 16 17 18

/*
 * tunables
 */
19 20 21 22
static const int cfq_quantum = 4;		/* max queue in one round of service */
static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
static const int cfq_back_max = 16 * 1024;	/* maximum backwards seek, in KiB */
static const int cfq_back_penalty = 2;		/* penalty of a backwards seek */
Linus Torvalds's avatar
Linus Torvalds committed
23

24
static const int cfq_slice_sync = HZ / 10;
Jens Axboe's avatar
Jens Axboe committed
25
static int cfq_slice_async = HZ / 25;
26
static const int cfq_slice_async_rq = 2;
27
static int cfq_slice_idle = HZ / 125;
28 29 30 31 32 33

#define CFQ_IDLE_GRACE		(HZ / 10)
#define CFQ_SLICE_SCALE		(5)

#define CFQ_KEY_ASYNC		(0)

Linus Torvalds's avatar
Linus Torvalds committed
34 35 36 37 38 39 40 41 42
/*
 * for the hash of cfqq inside the cfqd
 */
#define CFQ_QHASH_SHIFT		6
#define CFQ_QHASH_ENTRIES	(1 << CFQ_QHASH_SHIFT)
#define list_entry_qhash(entry)	hlist_entry((entry), struct cfq_queue, cfq_hash)

#define list_entry_cfqq(ptr)	list_entry((ptr), struct cfq_queue, cfq_list)

Jens Axboe's avatar
Jens Axboe committed
43 44
#define RQ_CIC(rq)		((struct cfq_io_context*)(rq)->elevator_private)
#define RQ_CFQQ(rq)		((rq)->elevator_private2)
Linus Torvalds's avatar
Linus Torvalds committed
45 46 47 48

static kmem_cache_t *cfq_pool;
static kmem_cache_t *cfq_ioc_pool;

49
static DEFINE_PER_CPU(unsigned long, ioc_count);
50 51
static struct completion *ioc_gone;

52 53 54 55
#define CFQ_PRIO_LISTS		IOPRIO_BE_NR
#define cfq_class_idle(cfqq)	((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
#define cfq_class_rt(cfqq)	((cfqq)->ioprio_class == IOPRIO_CLASS_RT)

Jens Axboe's avatar
Jens Axboe committed
56 57 58 59 60 61 62 63 64 65
#define ASYNC			(0)
#define SYNC			(1)

#define cfq_cfqq_dispatched(cfqq)	\
	((cfqq)->on_dispatch[ASYNC] + (cfqq)->on_dispatch[SYNC])

#define cfq_cfqq_class_sync(cfqq)	((cfqq)->key != CFQ_KEY_ASYNC)

#define cfq_cfqq_sync(cfqq)		\
	(cfq_cfqq_class_sync(cfqq) || (cfqq)->on_dispatch[SYNC])
66

67 68
#define sample_valid(samples)	((samples) > 80)

69 70 71
/*
 * Per block device queue structure
 */
Linus Torvalds's avatar
Linus Torvalds committed
72
struct cfq_data {
73 74 75 76 77 78 79 80 81 82 83 84 85 86
	request_queue_t *queue;

	/*
	 * rr list of queues with requests and the count of them
	 */
	struct list_head rr_list[CFQ_PRIO_LISTS];
	struct list_head busy_rr;
	struct list_head cur_rr;
	struct list_head idle_rr;
	unsigned int busy_queues;

	/*
	 * cfqq lookup hash
	 */
Linus Torvalds's avatar
Linus Torvalds committed
87 88
	struct hlist_head *cfq_hash;

89
	int rq_in_driver;
90
	int hw_tag;
Linus Torvalds's avatar
Linus Torvalds committed
91

92 93 94 95 96
	/*
	 * idle window management
	 */
	struct timer_list idle_slice_timer;
	struct work_struct unplug_work;
Linus Torvalds's avatar
Linus Torvalds committed
97

98 99 100 101 102 103
	struct cfq_queue *active_queue;
	struct cfq_io_context *active_cic;
	int cur_prio, cur_end_prio;
	unsigned int dispatch_slice;

	struct timer_list idle_class_timer;
Linus Torvalds's avatar
Linus Torvalds committed
104 105

	sector_t last_sector;
106
	unsigned long last_end_request;
Linus Torvalds's avatar
Linus Torvalds committed
107 108 109 110 111

	/*
	 * tunables, see top of file
	 */
	unsigned int cfq_quantum;
112
	unsigned int cfq_fifo_expire[2];
Linus Torvalds's avatar
Linus Torvalds committed
113 114
	unsigned int cfq_back_penalty;
	unsigned int cfq_back_max;
115 116 117
	unsigned int cfq_slice[2];
	unsigned int cfq_slice_async_rq;
	unsigned int cfq_slice_idle;
118 119

	struct list_head cic_list;
Linus Torvalds's avatar
Linus Torvalds committed
120 121
};

122 123 124
/*
 * Per process-grouping structure
 */
Linus Torvalds's avatar
Linus Torvalds committed
125 126 127 128 129
struct cfq_queue {
	/* reference count */
	atomic_t ref;
	/* parent cfq_data */
	struct cfq_data *cfqd;
130
	/* cfqq lookup hash */
Linus Torvalds's avatar
Linus Torvalds committed
131 132
	struct hlist_node cfq_hash;
	/* hash key */
133
	unsigned int key;
134
	/* member of the rr/busy/cur/idle cfqd list */
Linus Torvalds's avatar
Linus Torvalds committed
135 136 137 138
	struct list_head cfq_list;
	/* sorted list of pending requests */
	struct rb_root sort_list;
	/* if fifo isn't expired, next request to serve */
Jens Axboe's avatar
Jens Axboe committed
139
	struct request *next_rq;
Linus Torvalds's avatar
Linus Torvalds committed
140 141 142 143
	/* requests queued in sort_list */
	int queued[2];
	/* currently allocated requests */
	int allocated[2];
144 145
	/* pending metadata requests */
	int meta_pending;
Linus Torvalds's avatar
Linus Torvalds committed
146
	/* fifo list of requests in sort_list */
147
	struct list_head fifo;
Linus Torvalds's avatar
Linus Torvalds committed
148

149 150 151
	unsigned long slice_start;
	unsigned long slice_end;
	unsigned long slice_left;
Linus Torvalds's avatar
Linus Torvalds committed
152

Jens Axboe's avatar
Jens Axboe committed
153 154
	/* number of requests that are on the dispatch list */
	int on_dispatch[2];
155 156 157 158 159

	/* io prio of this group */
	unsigned short ioprio, org_ioprio;
	unsigned short ioprio_class, org_ioprio_class;

Jens Axboe's avatar
Jens Axboe committed
160 161
	/* various state flags, see below */
	unsigned int flags;
Linus Torvalds's avatar
Linus Torvalds committed
162 163
};

Jens Axboe's avatar
Jens Axboe committed
164 165 166 167 168 169 170 171 172
enum cfqq_state_flags {
	CFQ_CFQQ_FLAG_on_rr = 0,
	CFQ_CFQQ_FLAG_wait_request,
	CFQ_CFQQ_FLAG_must_alloc,
	CFQ_CFQQ_FLAG_must_alloc_slice,
	CFQ_CFQQ_FLAG_must_dispatch,
	CFQ_CFQQ_FLAG_fifo_expire,
	CFQ_CFQQ_FLAG_idle_window,
	CFQ_CFQQ_FLAG_prio_changed,
173
	CFQ_CFQQ_FLAG_queue_new,
Jens Axboe's avatar
Jens Axboe committed
174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197
};

#define CFQ_CFQQ_FNS(name)						\
static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq)		\
{									\
	cfqq->flags |= (1 << CFQ_CFQQ_FLAG_##name);			\
}									\
static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq)	\
{									\
	cfqq->flags &= ~(1 << CFQ_CFQQ_FLAG_##name);			\
}									\
static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq)		\
{									\
	return (cfqq->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0;	\
}

CFQ_CFQQ_FNS(on_rr);
CFQ_CFQQ_FNS(wait_request);
CFQ_CFQQ_FNS(must_alloc);
CFQ_CFQQ_FNS(must_alloc_slice);
CFQ_CFQQ_FNS(must_dispatch);
CFQ_CFQQ_FNS(fifo_expire);
CFQ_CFQQ_FNS(idle_window);
CFQ_CFQQ_FNS(prio_changed);
198
CFQ_CFQQ_FNS(queue_new);
Jens Axboe's avatar
Jens Axboe committed
199 200 201
#undef CFQ_CFQQ_FNS

static struct cfq_queue *cfq_find_cfq_hash(struct cfq_data *, unsigned int, unsigned short);
Jens Axboe's avatar
Jens Axboe committed
202
static void cfq_dispatch_insert(request_queue_t *, struct request *);
203
static struct cfq_queue *cfq_get_queue(struct cfq_data *cfqd, unsigned int key, struct task_struct *tsk, gfp_t gfp_mask);
Linus Torvalds's avatar
Linus Torvalds committed
204

Andrew Morton's avatar
Andrew Morton committed
205 206 207 208 209 210
/*
 * scheduler run of queue, if there are requests pending and no one in the
 * driver that will restart queueing
 */
static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
{
211
	if (cfqd->busy_queues)
Andrew Morton's avatar
Andrew Morton committed
212 213 214 215 216 217 218
		kblockd_schedule_work(&cfqd->unplug_work);
}

static int cfq_queue_empty(request_queue_t *q)
{
	struct cfq_data *cfqd = q->elevator->elevator_data;

219
	return !cfqd->busy_queues;
Andrew Morton's avatar
Andrew Morton committed
220 221
}

222 223
static inline pid_t cfq_queue_pid(struct task_struct *task, int rw)
{
Jens Axboe's avatar
Jens Axboe committed
224
	if (rw == READ || rw == WRITE_SYNC)
225 226 227 228 229
		return task->pid;

	return CFQ_KEY_ASYNC;
}

Linus Torvalds's avatar
Linus Torvalds committed
230
/*
Jens Axboe's avatar
Jens Axboe committed
231
 * Lifted from AS - choose which of rq1 and rq2 that is best served now.
Linus Torvalds's avatar
Linus Torvalds committed
232
 * We choose the request that is closest to the head right now. Distance
233
 * behind the head is penalized and only allowed to a certain extent.
Linus Torvalds's avatar
Linus Torvalds committed
234
 */
Jens Axboe's avatar
Jens Axboe committed
235 236
static struct request *
cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2)
Linus Torvalds's avatar
Linus Torvalds committed
237 238 239
{
	sector_t last, s1, s2, d1 = 0, d2 = 0;
	unsigned long back_max;
240 241 242
#define CFQ_RQ1_WRAP	0x01 /* request 1 wraps */
#define CFQ_RQ2_WRAP	0x02 /* request 2 wraps */
	unsigned wrap = 0; /* bit mask: requests behind the disk head? */
Linus Torvalds's avatar
Linus Torvalds committed
243

Jens Axboe's avatar
Jens Axboe committed
244 245 246 247
	if (rq1 == NULL || rq1 == rq2)
		return rq2;
	if (rq2 == NULL)
		return rq1;
248

Jens Axboe's avatar
Jens Axboe committed
249 250 251 252
	if (rq_is_sync(rq1) && !rq_is_sync(rq2))
		return rq1;
	else if (rq_is_sync(rq2) && !rq_is_sync(rq1))
		return rq2;
253 254 255 256
	if (rq_is_meta(rq1) && !rq_is_meta(rq2))
		return rq1;
	else if (rq_is_meta(rq2) && !rq_is_meta(rq1))
		return rq2;
Linus Torvalds's avatar
Linus Torvalds committed
257

Jens Axboe's avatar
Jens Axboe committed
258 259
	s1 = rq1->sector;
	s2 = rq2->sector;
Linus Torvalds's avatar
Linus Torvalds committed
260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277

	last = cfqd->last_sector;

	/*
	 * by definition, 1KiB is 2 sectors
	 */
	back_max = cfqd->cfq_back_max * 2;

	/*
	 * Strict one way elevator _except_ in the case where we allow
	 * short backward seeks which are biased as twice the cost of a
	 * similar forward seek.
	 */
	if (s1 >= last)
		d1 = s1 - last;
	else if (s1 + back_max >= last)
		d1 = (last - s1) * cfqd->cfq_back_penalty;
	else
278
		wrap |= CFQ_RQ1_WRAP;
Linus Torvalds's avatar
Linus Torvalds committed
279 280 281 282 283 284

	if (s2 >= last)
		d2 = s2 - last;
	else if (s2 + back_max >= last)
		d2 = (last - s2) * cfqd->cfq_back_penalty;
	else
285
		wrap |= CFQ_RQ2_WRAP;
Linus Torvalds's avatar
Linus Torvalds committed
286 287

	/* Found required data */
288 289 290 291 292 293

	/*
	 * By doing switch() on the bit mask "wrap" we avoid having to
	 * check two variables for all permutations: --> faster!
	 */
	switch (wrap) {
Jens Axboe's avatar
Jens Axboe committed
294
	case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
295
		if (d1 < d2)
Jens Axboe's avatar
Jens Axboe committed
296
			return rq1;
297
		else if (d2 < d1)
Jens Axboe's avatar
Jens Axboe committed
298
			return rq2;
299 300
		else {
			if (s1 >= s2)
Jens Axboe's avatar
Jens Axboe committed
301
				return rq1;
302
			else
Jens Axboe's avatar
Jens Axboe committed
303
				return rq2;
304
		}
Linus Torvalds's avatar
Linus Torvalds committed
305

306
	case CFQ_RQ2_WRAP:
Jens Axboe's avatar
Jens Axboe committed
307
		return rq1;
308
	case CFQ_RQ1_WRAP:
Jens Axboe's avatar
Jens Axboe committed
309 310
		return rq2;
	case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
311 312 313 314 315 316 317 318
	default:
		/*
		 * Since both rqs are wrapped,
		 * start with the one that's further behind head
		 * (--> only *one* back seek required),
		 * since back seek takes more time than forward.
		 */
		if (s1 <= s2)
Jens Axboe's avatar
Jens Axboe committed
319
			return rq1;
Linus Torvalds's avatar
Linus Torvalds committed
320
		else
Jens Axboe's avatar
Jens Axboe committed
321
			return rq2;
Linus Torvalds's avatar
Linus Torvalds committed
322 323 324 325 326 327
	}
}

/*
 * would be nice to take fifo expire time into account as well
 */
Jens Axboe's avatar
Jens Axboe committed
328 329 330
static struct request *
cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
		  struct request *last)
Linus Torvalds's avatar
Linus Torvalds committed
331
{
332 333
	struct rb_node *rbnext = rb_next(&last->rb_node);
	struct rb_node *rbprev = rb_prev(&last->rb_node);
Jens Axboe's avatar
Jens Axboe committed
334
	struct request *next = NULL, *prev = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
335

336
	BUG_ON(RB_EMPTY_NODE(&last->rb_node));
Linus Torvalds's avatar
Linus Torvalds committed
337 338

	if (rbprev)
Jens Axboe's avatar
Jens Axboe committed
339
		prev = rb_entry_rq(rbprev);
Linus Torvalds's avatar
Linus Torvalds committed
340

341
	if (rbnext)
Jens Axboe's avatar
Jens Axboe committed
342
		next = rb_entry_rq(rbnext);
343 344 345
	else {
		rbnext = rb_first(&cfqq->sort_list);
		if (rbnext && rbnext != &last->rb_node)
Jens Axboe's avatar
Jens Axboe committed
346
			next = rb_entry_rq(rbnext);
347
	}
Linus Torvalds's avatar
Linus Torvalds committed
348

349
	return cfq_choose_req(cfqd, next, prev);
Linus Torvalds's avatar
Linus Torvalds committed
350 351
}

352
static void cfq_resort_rr_list(struct cfq_queue *cfqq, int preempted)
Linus Torvalds's avatar
Linus Torvalds committed
353
{
354
	struct cfq_data *cfqd = cfqq->cfqd;
355
	struct list_head *list;
Linus Torvalds's avatar
Linus Torvalds committed
356

Jens Axboe's avatar
Jens Axboe committed
357
	BUG_ON(!cfq_cfqq_on_rr(cfqq));
Linus Torvalds's avatar
Linus Torvalds committed
358

359
	list_del(&cfqq->cfq_list);
Linus Torvalds's avatar
Linus Torvalds committed
360

361 362 363 364 365 366 367 368 369 370 371 372
	if (cfq_class_rt(cfqq))
		list = &cfqd->cur_rr;
	else if (cfq_class_idle(cfqq))
		list = &cfqd->idle_rr;
	else {
		/*
		 * if cfqq has requests in flight, don't allow it to be
		 * found in cfq_set_active_queue before it has finished them.
		 * this is done to increase fairness between a process that
		 * has lots of io pending vs one that only generates one
		 * sporadically or synchronously
		 */
Jens Axboe's avatar
Jens Axboe committed
373
		if (cfq_cfqq_dispatched(cfqq))
374 375 376
			list = &cfqd->busy_rr;
		else
			list = &cfqd->rr_list[cfqq->ioprio];
Linus Torvalds's avatar
Linus Torvalds committed
377 378
	}

379
	/*
380 381 382
	 * If this queue was preempted or is new (never been serviced), let
	 * it be added first for fairness but beind other new queues.
	 * Otherwise, just add to the back  of the list.
383
	 */
384 385 386
	if (preempted || cfq_cfqq_queue_new(cfqq)) {
		struct list_head *n = list;
		struct cfq_queue *__cfqq;
387

388 389 390 391
		while (n->next != list) {
			__cfqq = list_entry_cfqq(n->next);
			if (!cfq_cfqq_queue_new(__cfqq))
				break;
Linus Torvalds's avatar
Linus Torvalds committed
392

393 394
			n = n->next;
		}
Linus Torvalds's avatar
Linus Torvalds committed
395

396
		list = n;
Linus Torvalds's avatar
Linus Torvalds committed
397 398
	}

399
	list_add_tail(&cfqq->cfq_list, list);
Linus Torvalds's avatar
Linus Torvalds committed
400 401 402 403
}

/*
 * add to busy list of queues for service, trying to be fair in ordering
404
 * the pending list according to last request service
Linus Torvalds's avatar
Linus Torvalds committed
405 406
 */
static inline void
407
cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
408
{
Jens Axboe's avatar
Jens Axboe committed
409 410
	BUG_ON(cfq_cfqq_on_rr(cfqq));
	cfq_mark_cfqq_on_rr(cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
411 412
	cfqd->busy_queues++;

413
	cfq_resort_rr_list(cfqq, 0);
Linus Torvalds's avatar
Linus Torvalds committed
414 415 416 417 418
}

static inline void
cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
Jens Axboe's avatar
Jens Axboe committed
419 420
	BUG_ON(!cfq_cfqq_on_rr(cfqq));
	cfq_clear_cfqq_on_rr(cfqq);
421
	list_del_init(&cfqq->cfq_list);
Linus Torvalds's avatar
Linus Torvalds committed
422 423 424 425 426 427 428 429

	BUG_ON(!cfqd->busy_queues);
	cfqd->busy_queues--;
}

/*
 * rb tree support functions
 */
Jens Axboe's avatar
Jens Axboe committed
430
static inline void cfq_del_rq_rb(struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
431
{
Jens Axboe's avatar
Jens Axboe committed
432
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
433
	struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboe's avatar
Jens Axboe committed
434
	const int sync = rq_is_sync(rq);
Linus Torvalds's avatar
Linus Torvalds committed
435

436 437
	BUG_ON(!cfqq->queued[sync]);
	cfqq->queued[sync]--;
Linus Torvalds's avatar
Linus Torvalds committed
438

Jens Axboe's avatar
Jens Axboe committed
439
	elv_rb_del(&cfqq->sort_list, rq);
Linus Torvalds's avatar
Linus Torvalds committed
440

441
	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
442
		cfq_del_cfqq_rr(cfqd, cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
443 444
}

Jens Axboe's avatar
Jens Axboe committed
445
static void cfq_add_rq_rb(struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
446
{
Jens Axboe's avatar
Jens Axboe committed
447
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
Linus Torvalds's avatar
Linus Torvalds committed
448
	struct cfq_data *cfqd = cfqq->cfqd;
449
	struct request *__alias;
Linus Torvalds's avatar
Linus Torvalds committed
450

451
	cfqq->queued[rq_is_sync(rq)]++;
Linus Torvalds's avatar
Linus Torvalds committed
452 453 454 455 456

	/*
	 * looks a little odd, but the first insert might return an alias.
	 * if that happens, put the alias on the dispatch list
	 */
457
	while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
Jens Axboe's avatar
Jens Axboe committed
458
		cfq_dispatch_insert(cfqd->queue, __alias);
459 460 461

	if (!cfq_cfqq_on_rr(cfqq))
		cfq_add_cfqq_rr(cfqd, cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
462 463 464
}

static inline void
Jens Axboe's avatar
Jens Axboe committed
465
cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
466
{
467 468
	elv_rb_del(&cfqq->sort_list, rq);
	cfqq->queued[rq_is_sync(rq)]--;
Jens Axboe's avatar
Jens Axboe committed
469
	cfq_add_rq_rb(rq);
Linus Torvalds's avatar
Linus Torvalds committed
470 471
}

472 473
static struct request *
cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
Linus Torvalds's avatar
Linus Torvalds committed
474
{
475 476 477
	struct task_struct *tsk = current;
	pid_t key = cfq_queue_pid(tsk, bio_data_dir(bio));
	struct cfq_queue *cfqq;
Linus Torvalds's avatar
Linus Torvalds committed
478

479
	cfqq = cfq_find_cfq_hash(cfqd, key, tsk->ioprio);
480 481 482
	if (cfqq) {
		sector_t sector = bio->bi_sector + bio_sectors(bio);

483
		return elv_rb_find(&cfqq->sort_list, sector);
484
	}
Linus Torvalds's avatar
Linus Torvalds committed
485 486 487 488

	return NULL;
}

489
static void cfq_activate_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
490
{
491
	struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe's avatar
Jens Axboe committed
492

493
	cfqd->rq_in_driver++;
494 495 496 497 498 499 500 501 502

	/*
	 * If the depth is larger 1, it really could be queueing. But lets
	 * make the mark a little higher - idling could still be good for
	 * low queueing, and a low queueing number could also just indicate
	 * a SCSI mid layer like behaviour where limit+1 is often seen.
	 */
	if (!cfqd->hw_tag && cfqd->rq_in_driver > 4)
		cfqd->hw_tag = 1;
Linus Torvalds's avatar
Linus Torvalds committed
503 504
}

505
static void cfq_deactivate_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
506
{
507 508 509 510
	struct cfq_data *cfqd = q->elevator->elevator_data;

	WARN_ON(!cfqd->rq_in_driver);
	cfqd->rq_in_driver--;
Linus Torvalds's avatar
Linus Torvalds committed
511 512
}

513
static void cfq_remove_request(struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
514
{
Jens Axboe's avatar
Jens Axboe committed
515
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
516

Jens Axboe's avatar
Jens Axboe committed
517 518
	if (cfqq->next_rq == rq)
		cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
Linus Torvalds's avatar
Linus Torvalds committed
519

520
	list_del_init(&rq->queuelist);
Jens Axboe's avatar
Jens Axboe committed
521
	cfq_del_rq_rb(rq);
522 523 524 525 526

	if (rq_is_meta(rq)) {
		WARN_ON(!cfqq->meta_pending);
		cfqq->meta_pending--;
	}
Linus Torvalds's avatar
Linus Torvalds committed
527 528 529 530 531 532 533 534
}

static int
cfq_merge(request_queue_t *q, struct request **req, struct bio *bio)
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	struct request *__rq;

535
	__rq = cfq_find_rq_fmerge(cfqd, bio);
536
	if (__rq && elv_rq_merge_ok(__rq, bio)) {
537 538
		*req = __rq;
		return ELEVATOR_FRONT_MERGE;
Linus Torvalds's avatar
Linus Torvalds committed
539 540 541 542 543
	}

	return ELEVATOR_NO_MERGE;
}

544 545
static void cfq_merged_request(request_queue_t *q, struct request *req,
			       int type)
Linus Torvalds's avatar
Linus Torvalds committed
546
{
547
	if (type == ELEVATOR_FRONT_MERGE) {
Jens Axboe's avatar
Jens Axboe committed
548
		struct cfq_queue *cfqq = RQ_CFQQ(req);
Linus Torvalds's avatar
Linus Torvalds committed
549

Jens Axboe's avatar
Jens Axboe committed
550
		cfq_reposition_rq_rb(cfqq, req);
Linus Torvalds's avatar
Linus Torvalds committed
551 552 553 554 555 556 557
	}
}

static void
cfq_merged_requests(request_queue_t *q, struct request *rq,
		    struct request *next)
{
558 559 560 561 562 563 564
	/*
	 * reposition in fifo if next is older than rq
	 */
	if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
	    time_before(next->start_time, rq->start_time))
		list_move(&rq->queuelist, &next->queuelist);

565
	cfq_remove_request(next);
566 567 568 569 570 571 572 573 574 575 576 577 578 579
}

static inline void
__cfq_set_active_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	if (cfqq) {
		/*
		 * stop potential idle class queues waiting service
		 */
		del_timer(&cfqd->idle_class_timer);

		cfqq->slice_start = jiffies;
		cfqq->slice_end = 0;
		cfqq->slice_left = 0;
Jens Axboe's avatar
Jens Axboe committed
580 581
		cfq_clear_cfqq_must_alloc_slice(cfqq);
		cfq_clear_cfqq_fifo_expire(cfqq);
582 583 584 585 586
	}

	cfqd->active_queue = cfqq;
}

587 588 589 590 591 592 593 594 595 596 597 598
/*
 * current cfqq expired its slice (or was too idle), select new one
 */
static void
__cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
		    int preempted)
{
	unsigned long now = jiffies;

	if (cfq_cfqq_wait_request(cfqq))
		del_timer(&cfqd->idle_slice_timer);

599
	if (!preempted && !cfq_cfqq_dispatched(cfqq))
600 601 602 603
		cfq_schedule_dispatch(cfqd);

	cfq_clear_cfqq_must_dispatch(cfqq);
	cfq_clear_cfqq_wait_request(cfqq);
604
	cfq_clear_cfqq_queue_new(cfqq);
605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636

	/*
	 * store what was left of this slice, if the queue idled out
	 * or was preempted
	 */
	if (time_after(cfqq->slice_end, now))
		cfqq->slice_left = cfqq->slice_end - now;
	else
		cfqq->slice_left = 0;

	if (cfq_cfqq_on_rr(cfqq))
		cfq_resort_rr_list(cfqq, preempted);

	if (cfqq == cfqd->active_queue)
		cfqd->active_queue = NULL;

	if (cfqd->active_cic) {
		put_io_context(cfqd->active_cic->ioc);
		cfqd->active_cic = NULL;
	}

	cfqd->dispatch_slice = 0;
}

static inline void cfq_slice_expired(struct cfq_data *cfqd, int preempted)
{
	struct cfq_queue *cfqq = cfqd->active_queue;

	if (cfqq)
		__cfq_slice_expired(cfqd, cfqq, preempted);
}

637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670
/*
 * 0
 * 0,1
 * 0,1,2
 * 0,1,2,3
 * 0,1,2,3,4
 * 0,1,2,3,4,5
 * 0,1,2,3,4,5,6
 * 0,1,2,3,4,5,6,7
 */
static int cfq_get_next_prio_level(struct cfq_data *cfqd)
{
	int prio, wrap;

	prio = -1;
	wrap = 0;
	do {
		int p;

		for (p = cfqd->cur_prio; p <= cfqd->cur_end_prio; p++) {
			if (!list_empty(&cfqd->rr_list[p])) {
				prio = p;
				break;
			}
		}

		if (prio != -1)
			break;
		cfqd->cur_prio = 0;
		if (++cfqd->cur_end_prio == CFQ_PRIO_LISTS) {
			cfqd->cur_end_prio = 0;
			if (wrap)
				break;
			wrap = 1;
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
	} while (1);

	if (unlikely(prio == -1))
		return -1;

	BUG_ON(prio >= CFQ_PRIO_LISTS);

	list_splice_init(&cfqd->rr_list[prio], &cfqd->cur_rr);

	cfqd->cur_prio = prio + 1;
	if (cfqd->cur_prio > cfqd->cur_end_prio) {
		cfqd->cur_end_prio = cfqd->cur_prio;
		cfqd->cur_prio = 0;
	}
	if (cfqd->cur_end_prio == CFQ_PRIO_LISTS) {
		cfqd->cur_prio = 0;
		cfqd->cur_end_prio = 0;
Linus Torvalds's avatar
Linus Torvalds committed
689 690
	}

691 692 693
	return prio;
}

Jens Axboe's avatar
Jens Axboe committed
694
static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd)
695
{
696
	struct cfq_queue *cfqq = NULL;
697

698 699 700 701 702 703
	if (!list_empty(&cfqd->cur_rr) || cfq_get_next_prio_level(cfqd) != -1) {
		/*
		 * if current list is non-empty, grab first entry. if it is
		 * empty, get next prio level and grab first entry then if any
		 * are spliced
		 */
704
		cfqq = list_entry_cfqq(cfqd->cur_rr.next);
705 706 707 708 709
	} else if (!list_empty(&cfqd->busy_rr)) {
		/*
		 * If no new queues are available, check if the busy list has
		 * some before falling back to idle io.
		 */
710
		cfqq = list_entry_cfqq(cfqd->busy_rr.next);
711 712 713 714 715 716
	} else if (!list_empty(&cfqd->idle_rr)) {
		/*
		 * if we have idle queues and no rt or be queues had pending
		 * requests, either allow immediate service if the grace period
		 * has passed or arm the idle grace timer
		 */
717 718 719 720 721 722 723 724 725
		unsigned long end = cfqd->last_end_request + CFQ_IDLE_GRACE;

		if (time_after_eq(jiffies, end))
			cfqq = list_entry_cfqq(cfqd->idle_rr.next);
		else
			mod_timer(&cfqd->idle_class_timer, end);
	}

	__cfq_set_active_queue(cfqd, cfqq);
Jens Axboe's avatar
Jens Axboe committed
726
	return cfqq;
727 728
}

729 730
#define CIC_SEEKY(cic) ((cic)->seek_mean > (128 * 1024))

731 732 733
static int cfq_arm_slice_timer(struct cfq_data *cfqd, struct cfq_queue *cfqq)

{
734
	struct cfq_io_context *cic;
735 736
	unsigned long sl;

737
	WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
738 739 740 741 742 743 744
	WARN_ON(cfqq != cfqd->active_queue);

	/*
	 * idle is disabled, either manually or by past process history
	 */
	if (!cfqd->cfq_slice_idle)
		return 0;
Jens Axboe's avatar
Jens Axboe committed
745
	if (!cfq_cfqq_idle_window(cfqq))
746 747 748 749
		return 0;
	/*
	 * task has exited, don't wait
	 */
750 751
	cic = cfqd->active_cic;
	if (!cic || !cic->ioc->task)
752 753
		return 0;

Jens Axboe's avatar
Jens Axboe committed
754 755
	cfq_mark_cfqq_must_dispatch(cfqq);
	cfq_mark_cfqq_wait_request(cfqq);
756

757
	sl = min(cfqq->slice_end - 1, (unsigned long) cfqd->cfq_slice_idle);
758 759 760 761 762 763

	/*
	 * we don't want to idle for seeks, but we do want to allow
	 * fair distribution of slice time for a process doing back-to-back
	 * seeks. so allow a little bit of time for him to submit a new rq
	 */
764
	if (sample_valid(cic->seek_samples) && CIC_SEEKY(cic))
765
		sl = min(sl, msecs_to_jiffies(2));
766

767
	mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
768
	return 1;
Linus Torvalds's avatar
Linus Torvalds committed
769 770
}

Jens Axboe's avatar
Jens Axboe committed
771
static void cfq_dispatch_insert(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
772 773
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe's avatar
Jens Axboe committed
774
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
775

776 777 778
	cfq_remove_request(rq);
	cfqq->on_dispatch[rq_is_sync(rq)]++;
	elv_dispatch_sort(q, rq);
779 780 781

	rq = list_entry(q->queue_head.prev, struct request, queuelist);
	cfqd->last_sector = rq->sector + rq->nr_sectors;
Linus Torvalds's avatar
Linus Torvalds committed
782 783 784 785 786
}

/*
 * return expired entry, or NULL to just start from scratch in rbtree
 */
Jens Axboe's avatar
Jens Axboe committed
787
static inline struct request *cfq_check_fifo(struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
788 789
{
	struct cfq_data *cfqd = cfqq->cfqd;
790
	struct request *rq;
791
	int fifo;
Linus Torvalds's avatar
Linus Torvalds committed
792

Jens Axboe's avatar
Jens Axboe committed
793
	if (cfq_cfqq_fifo_expire(cfqq))
Linus Torvalds's avatar
Linus Torvalds committed
794
		return NULL;
795 796
	if (list_empty(&cfqq->fifo))
		return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
797

798 799
	fifo = cfq_cfqq_class_sync(cfqq);
	rq = rq_entry_fifo(cfqq->fifo.next);
Linus Torvalds's avatar
Linus Torvalds committed
800

801 802 803
	if (time_after(jiffies, rq->start_time + cfqd->cfq_fifo_expire[fifo])) {
		cfq_mark_cfqq_fifo_expire(cfqq);
		return rq;
Linus Torvalds's avatar
Linus Torvalds committed
804 805 806 807 808 809
	}

	return NULL;
}

/*
Jens Axboe's avatar
Jens Axboe committed
810 811 812
 * Scale schedule slice based on io priority. Use the sync time slice only
 * if a queue is marked sync and has sync io queued. A sync queue with async
 * io only, should not get full sync slice length.
Linus Torvalds's avatar
Linus Torvalds committed
813
 */
814 815 816 817 818 819 820 821 822 823
static inline int
cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	const int base_slice = cfqd->cfq_slice[cfq_cfqq_sync(cfqq)];

	WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);

	return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - cfqq->ioprio));
}

Linus Torvalds's avatar
Linus Torvalds committed
824
static inline void
825
cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
826
{
827 828
	cfqq->slice_end = cfq_prio_to_slice(cfqd, cfqq) + jiffies;
}
Linus Torvalds's avatar
Linus Torvalds committed
829

830 831 832 833
static inline int
cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
	const int base_rq = cfqd->cfq_slice_async_rq;
Linus Torvalds's avatar
Linus Torvalds committed
834

835
	WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
Linus Torvalds's avatar
Linus Torvalds committed
836

837
	return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
Linus Torvalds's avatar
Linus Torvalds committed
838 839
}

840 841 842
/*
 * get next queue for service
 */
843
static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
Linus Torvalds's avatar
Linus Torvalds committed
844
{
845
	unsigned long now = jiffies;
Linus Torvalds's avatar
Linus Torvalds committed
846 847
	struct cfq_queue *cfqq;

848 849 850
	cfqq = cfqd->active_queue;
	if (!cfqq)
		goto new_queue;
Linus Torvalds's avatar
Linus Torvalds committed
851

852 853 854
	/*
	 * slice has expired
	 */
Jens Axboe's avatar
Jens Axboe committed
855 856
	if (!cfq_cfqq_must_dispatch(cfqq) && time_after(now, cfqq->slice_end))
		goto expire;
Linus Torvalds's avatar
Linus Torvalds committed
857

858 859 860 861
	/*
	 * if queue has requests, dispatch one. if not, check if
	 * enough slice is left to wait for one
	 */
862
	if (!RB_EMPTY_ROOT(&cfqq->sort_list))
863
		goto keep_queue;
864 865 866 867
	else if (cfq_cfqq_dispatched(cfqq)) {
		cfqq = NULL;
		goto keep_queue;
	} else if (cfq_cfqq_class_sync(cfqq)) {
868 869 870 871
		if (cfq_arm_slice_timer(cfqd, cfqq))
			return NULL;
	}

Jens Axboe's avatar
Jens Axboe committed
872
expire:
873
	cfq_slice_expired(cfqd, 0);
Jens Axboe's avatar
Jens Axboe committed
874 875
new_queue:
	cfqq = cfq_set_active_queue(cfqd);
876
keep_queue:
Jens Axboe's avatar
Jens Axboe committed
877
	return cfqq;
878 879 880 881 882 883 884 885
}

static int
__cfq_dispatch_requests(struct cfq_data *cfqd, struct cfq_queue *cfqq,
			int max_dispatch)
{
	int dispatched = 0;

886
	BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
887 888

	do {
Jens Axboe's avatar
Jens Axboe committed
889
		struct request *rq;
Linus Torvalds's avatar
Linus Torvalds committed
890 891

		/*
892
		 * follow expired path, else get first next available
Linus Torvalds's avatar
Linus Torvalds committed
893
		 */
Jens Axboe's avatar
Jens Axboe committed
894 895
		if ((rq = cfq_check_fifo(cfqq)) == NULL)
			rq = cfqq->next_rq;
896 897 898 899

		/*
		 * finally, insert request into driver dispatch list
		 */
Jens Axboe's avatar
Jens Axboe committed
900
		cfq_dispatch_insert(cfqd->queue, rq);
Linus Torvalds's avatar
Linus Torvalds committed
901

902 903
		cfqd->dispatch_slice++;
		dispatched++;
Linus Torvalds's avatar
Linus Torvalds committed
904

905
		if (!cfqd->active_cic) {
Jens Axboe's avatar
Jens Axboe committed
906 907
			atomic_inc(&RQ_CIC(rq)->ioc->refcount);
			cfqd->active_cic = RQ_CIC(rq);
908
		}
Linus Torvalds's avatar
Linus Torvalds committed
909

910
		if (RB_EMPTY_ROOT(&cfqq->sort_list))
911 912 913 914 915
			break;

	} while (dispatched < max_dispatch);

	/*
916
	 * if slice end isn't set yet, set it.
917 918 919 920 921 922 923 924 925 926
	 */
	if (!cfqq->slice_end)
		cfq_set_prio_slice(cfqd, cfqq);

	/*
	 * expire an async queue immediately if it has used up its slice. idle
	 * queue always expire after 1 dispatch round.
	 */
	if ((!cfq_cfqq_sync(cfqq) &&
	    cfqd->dispatch_slice >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
927 928
	    cfq_class_idle(cfqq) ||
	    !cfq_cfqq_idle_window(cfqq))
929 930 931 932 933
		cfq_slice_expired(cfqd, 0);

	return dispatched;
}

934 935 936 937
static int
cfq_forced_dispatch_cfqqs(struct list_head *list)
{
	struct cfq_queue *cfqq, *next;
938
	int dispatched;
939

940
	dispatched = 0;
941
	list_for_each_entry_safe(cfqq, next, list, cfq_list) {
Jens Axboe's avatar
Jens Axboe committed
942 943
		while (cfqq->next_rq) {
			cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
944 945 946 947
			dispatched++;
		}
		BUG_ON(!list_empty(&cfqq->fifo));
	}
948

949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970
	return dispatched;
}

static int
cfq_forced_dispatch(struct cfq_data *cfqd)
{
	int i, dispatched = 0;

	for (i = 0; i < CFQ_PRIO_LISTS; i++)
		dispatched += cfq_forced_dispatch_cfqqs(&cfqd->rr_list[i]);

	dispatched += cfq_forced_dispatch_cfqqs(&cfqd->busy_rr);
	dispatched += cfq_forced_dispatch_cfqqs(&cfqd->cur_rr);
	dispatched += cfq_forced_dispatch_cfqqs(&cfqd->idle_rr);

	cfq_slice_expired(cfqd, 0);

	BUG_ON(cfqd->busy_queues);

	return dispatched;
}

971
static int
972
cfq_dispatch_requests(request_queue_t *q, int force)
973 974
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
975 976
	struct cfq_queue *cfqq, *prev_cfqq;
	int dispatched;
977 978 979 980

	if (!cfqd->busy_queues)
		return 0;

981 982 983
	if (unlikely(force))
		return cfq_forced_dispatch(cfqd);

984 985 986
	dispatched = 0;
	prev_cfqq = NULL;
	while ((cfqq = cfq_select_queue(cfqd)) != NULL) {
987 988
		int max_dispatch;

989 990 991 992 993 994
		/*
		 * Don't repeat dispatch from the previous queue.
		 */
		if (prev_cfqq == cfqq)
			break;

Jens Axboe's avatar
Jens Axboe committed
995 996
		cfq_clear_cfqq_must_dispatch(cfqq);
		cfq_clear_cfqq_wait_request(cfqq);
997 998
		del_timer(&cfqd->idle_slice_timer);

999 1000 1001
		max_dispatch = cfqd->cfq_quantum;
		if (cfq_class_idle(cfqq))
			max_dispatch = 1;
Linus Torvalds's avatar
Linus Torvalds committed
1002

1003 1004 1005 1006 1007 1008 1009 1010 1011 1012
		dispatched += __cfq_dispatch_requests(cfqd, cfqq, max_dispatch);

		/*
		 * If the dispatch cfqq has idling enabled and is still
		 * the active queue, break out.
		 */
		if (cfq_cfqq_idle_window(cfqq) && cfqd->active_queue)
			break;

		prev_cfqq = cfqq;
Linus Torvalds's avatar
Linus Torvalds committed
1013 1014
	}

1015
	return dispatched;
Linus Torvalds's avatar
Linus Torvalds committed
1016 1017 1018
}

/*
Jens Axboe's avatar
Jens Axboe committed
1019 1020
 * task holds one reference to the queue, dropped when task exits. each rq
 * in-flight on this queue also holds a reference, dropped when rq is freed.
Linus Torvalds's avatar
Linus Torvalds committed
1021 1022 1023 1024 1025
 *
 * queue lock must be held here.
 */
static void cfq_put_queue(struct cfq_queue *cfqq)
{
1026 1027 1028
	struct cfq_data *cfqd = cfqq->cfqd;

	BUG_ON(atomic_read(&cfqq->ref) <= 0);
Linus Torvalds's avatar
Linus Torvalds committed
1029 1030 1031 1032 1033

	if (!atomic_dec_and_test(&cfqq->ref))
		return;

	BUG_ON(rb_first(&cfqq->sort_list));
1034
	BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
Jens Axboe's avatar
Jens Axboe committed
1035
	BUG_ON(cfq_cfqq_on_rr(cfqq));
Linus Torvalds's avatar
Linus Torvalds committed
1036

1037
	if (unlikely(cfqd->active_queue == cfqq))
Jens Axboe's avatar
Jens Axboe committed
1038
		__cfq_slice_expired(cfqd, cfqq, 0);
1039

Linus Torvalds's avatar
Linus Torvalds committed
1040 1041 1042 1043 1044 1045 1046 1047
	/*
	 * it's on the empty list and still hashed
	 */
	list_del(&cfqq->cfq_list);
	hlist_del(&cfqq->cfq_hash);
	kmem_cache_free(cfq_pool, cfqq);
}

Jens Axboe's avatar
Jens Axboe committed
1048
static struct cfq_queue *
Jens Axboe's avatar
Jens Axboe committed
1049 1050
__cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned int prio,
		    const int hashval)
Linus Torvalds's avatar
Linus Torvalds committed
1051 1052
{
	struct hlist_head *hash_list = &cfqd->cfq_hash[hashval];
1053 1054
	struct hlist_node *entry;
	struct cfq_queue *__cfqq;
Linus Torvalds's avatar
Linus Torvalds committed
1055

1056
	hlist_for_each_entry(__cfqq, entry, hash_list, cfq_hash) {
Al Viro's avatar
Al Viro committed
1057
		const unsigned short __p = IOPRIO_PRIO_VALUE(__cfqq->org_ioprio_class, __cfqq->org_ioprio);
Linus Torvalds's avatar
Linus Torvalds committed
1058

1059
		if (__cfqq->key == key && (__p == prio || !prio))
Linus Torvalds's avatar
Linus Torvalds committed
1060 1061 1062 1063 1064 1065 1066
			return __cfqq;
	}

	return NULL;
}

static struct cfq_queue *
Jens Axboe's avatar
Jens Axboe committed
1067
cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned short prio)
Linus Torvalds's avatar
Linus Torvalds committed
1068
{
Jens Axboe's avatar
Jens Axboe committed
1069
	return __cfq_find_cfq_hash(cfqd, key, prio, hash_long(key, CFQ_QHASH_SHIFT));
Linus Torvalds's avatar
Linus Torvalds committed
1070 1071
}

1072
static void cfq_free_io_context(struct io_context *ioc)
Linus Torvalds's avatar
Linus Torvalds committed
1073
{
1074
	struct cfq_io_context *__cic;
1075 1076
	struct rb_node *n;
	int freed = 0;
Linus Torvalds's avatar
Linus Torvalds committed
1077

1078 1079 1080
	while ((n = rb_first(&ioc->cic_root)) != NULL) {
		__cic = rb_entry(n, struct cfq_io_context, rb_node);
		rb_erase(&__cic->rb_node, &ioc->cic_root);
1081
		kmem_cache_free(cfq_ioc_pool, __cic);
1082
		freed++;
Linus Torvalds's avatar
Linus Torvalds committed
1083 1084
	}

1085 1086 1087
	elv_ioc_count_mod(ioc_count, -freed);

	if (ioc_gone && !elv_ioc_count_read(ioc_count))
1088
		complete(ioc_gone);
Linus Torvalds's avatar
Linus Torvalds committed
1089 1090
}

1091
static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
1092
{
1093 1094
	if (unlikely(cfqq == cfqd->active_queue))
		__cfq_slice_expired(cfqd, cfqq, 0);
1095

1096 1097
	cfq_put_queue(cfqq);
}
1098

1099 1100