cfq-iosched.c 51.1 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6 7 8 9
/*
 *  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.
 *
 *  Copyright (C) 2003 Jens Axboe <axboe@suse.de>
 */
#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);
Linus Torvalds's avatar
Linus Torvalds committed
459 460 461
}

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

469 470
static struct request *
cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
Linus Torvalds's avatar
Linus Torvalds committed
471
{
472 473 474
	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
475

476
	cfqq = cfq_find_cfq_hash(cfqd, key, tsk->ioprio);
477 478 479
	if (cfqq) {
		sector_t sector = bio->bi_sector + bio_sectors(bio);

480
		return elv_rb_find(&cfqq->sort_list, sector);
481
	}
Linus Torvalds's avatar
Linus Torvalds committed
482 483 484 485

	return NULL;
}

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

490
	cfqd->rq_in_driver++;
491 492 493 494 495 496 497 498 499

	/*
	 * 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
500 501
}

502
static void cfq_deactivate_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
503
{
504 505 506 507
	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
508 509
}

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

Jens Axboe's avatar
Jens Axboe committed
514 515
	if (cfqq->next_rq == rq)
		cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
Linus Torvalds's avatar
Linus Torvalds committed
516

517
	list_del_init(&rq->queuelist);
Jens Axboe's avatar
Jens Axboe committed
518
	cfq_del_rq_rb(rq);
519 520 521 522 523

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

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;

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

	return ELEVATOR_NO_MERGE;
}

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

Jens Axboe's avatar
Jens Axboe committed
547
		cfq_reposition_rq_rb(cfqq, req);
Linus Torvalds's avatar
Linus Torvalds committed
548 549 550 551 552 553 554
	}
}

static void
cfq_merged_requests(request_queue_t *q, struct request *rq,
		    struct request *next)
{
555 556 557 558 559 560 561
	/*
	 * 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);

562
	cfq_remove_request(next);
563 564 565 566 567 568 569 570 571 572 573 574 575 576
}

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
577 578
		cfq_clear_cfqq_must_alloc_slice(cfqq);
		cfq_clear_cfqq_fifo_expire(cfqq);
579 580 581 582 583
	}

	cfqd->active_queue = cfqq;
}

584 585 586 587 588 589 590 591 592 593 594 595
/*
 * 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);

596
	if (!preempted && !cfq_cfqq_dispatched(cfqq))
597 598 599 600
		cfq_schedule_dispatch(cfqd);

	cfq_clear_cfqq_must_dispatch(cfqq);
	cfq_clear_cfqq_wait_request(cfqq);
601
	cfq_clear_cfqq_queue_new(cfqq);
602 603 604 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

	/*
	 * 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);
}

634 635 636 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
/*
 * 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
668
		}
669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685
	} 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
686 687
	}

688 689 690
	return prio;
}

Jens Axboe's avatar
Jens Axboe committed
691
static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd)
692
{
693
	struct cfq_queue *cfqq = NULL;
694

695 696 697 698 699 700
	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
		 */
701
		cfqq = list_entry_cfqq(cfqd->cur_rr.next);
702 703 704 705 706
	} 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.
		 */
707
		cfqq = list_entry_cfqq(cfqd->busy_rr.next);
708 709 710 711 712 713
	} 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
		 */
714 715 716 717 718 719 720 721 722
		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
723
	return cfqq;
724 725
}

726 727
#define CIC_SEEKY(cic) ((cic)->seek_mean > (128 * 1024))

728 729 730
static int cfq_arm_slice_timer(struct cfq_data *cfqd, struct cfq_queue *cfqq)

{
731
	struct cfq_io_context *cic;
732 733
	unsigned long sl;

734
	WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
735 736 737 738 739 740 741
	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
742
	if (!cfq_cfqq_idle_window(cfqq))
743 744 745 746
		return 0;
	/*
	 * task has exited, don't wait
	 */
747 748
	cic = cfqd->active_cic;
	if (!cic || !cic->ioc->task)
749 750
		return 0;

Jens Axboe's avatar
Jens Axboe committed
751 752
	cfq_mark_cfqq_must_dispatch(cfqq);
	cfq_mark_cfqq_wait_request(cfqq);
753

754
	sl = min(cfqq->slice_end - 1, (unsigned long) cfqd->cfq_slice_idle);
755 756 757 758 759 760

	/*
	 * 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
	 */
761
	if (sample_valid(cic->seek_samples) && CIC_SEEKY(cic))
762
		sl = min(sl, msecs_to_jiffies(2));
763

764
	mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
765
	return 1;
Linus Torvalds's avatar
Linus Torvalds committed
766 767
}

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

773 774 775
	cfq_remove_request(rq);
	cfqq->on_dispatch[rq_is_sync(rq)]++;
	elv_dispatch_sort(q, rq);
776 777 778

	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
779 780 781 782 783
}

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

Jens Axboe's avatar
Jens Axboe committed
790
	if (cfq_cfqq_fifo_expire(cfqq))
Linus Torvalds's avatar
Linus Torvalds committed
791
		return NULL;
792 793
	if (list_empty(&cfqq->fifo))
		return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
794

795 796
	fifo = cfq_cfqq_class_sync(cfqq);
	rq = rq_entry_fifo(cfqq->fifo.next);
Linus Torvalds's avatar
Linus Torvalds committed
797

798 799 800
	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
801 802 803 804 805 806
	}

	return NULL;
}

/*
Jens Axboe's avatar
Jens Axboe committed
807 808 809
 * 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
810
 */
811 812 813 814 815 816 817 818 819 820
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
821
static inline void
822
cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
823
{
824 825
	cfqq->slice_end = cfq_prio_to_slice(cfqd, cfqq) + jiffies;
}
Linus Torvalds's avatar
Linus Torvalds committed
826

827 828 829 830
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
831

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

834
	return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
Linus Torvalds's avatar
Linus Torvalds committed
835 836
}

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

845 846 847
	cfqq = cfqd->active_queue;
	if (!cfqq)
		goto new_queue;
Linus Torvalds's avatar
Linus Torvalds committed
848

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

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

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

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

883
	BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
884 885

	do {
Jens Axboe's avatar
Jens Axboe committed
886
		struct request *rq;
Linus Torvalds's avatar
Linus Torvalds committed
887 888

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

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

899 900
		cfqd->dispatch_slice++;
		dispatched++;
Linus Torvalds's avatar
Linus Torvalds committed
901

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

907
		if (RB_EMPTY_ROOT(&cfqq->sort_list))
908 909 910 911 912
			break;

	} while (dispatched < max_dispatch);

	/*
913
	 * if slice end isn't set yet, set it.
914 915 916 917 918 919 920 921 922 923
	 */
	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)) ||
924 925
	    cfq_class_idle(cfqq) ||
	    !cfq_cfqq_idle_window(cfqq))
926 927 928 929 930
		cfq_slice_expired(cfqd, 0);

	return dispatched;
}

931 932 933 934
static int
cfq_forced_dispatch_cfqqs(struct list_head *list)
{
	struct cfq_queue *cfqq, *next;
935
	int dispatched;
936

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

946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967
	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;
}

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

	if (!cfqd->busy_queues)
		return 0;

978 979 980
	if (unlikely(force))
		return cfq_forced_dispatch(cfqd);

981 982 983
	dispatched = 0;
	prev_cfqq = NULL;
	while ((cfqq = cfq_select_queue(cfqd)) != NULL) {
984 985
		int max_dispatch;

986 987 988 989 990 991
		/*
		 * Don't repeat dispatch from the previous queue.
		 */
		if (prev_cfqq == cfqq)
			break;

Jens Axboe's avatar
Jens Axboe committed
992 993
		cfq_clear_cfqq_must_dispatch(cfqq);
		cfq_clear_cfqq_wait_request(cfqq);
994 995
		del_timer(&cfqd->idle_slice_timer);

996 997 998
		max_dispatch = cfqd->cfq_quantum;
		if (cfq_class_idle(cfqq))
			max_dispatch = 1;
Linus Torvalds's avatar
Linus Torvalds committed
999

1000 1001 1002 1003 1004 1005 1006 1007 1008 1009
		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
1010 1011
	}

1012
	return dispatched;
Linus Torvalds's avatar
Linus Torvalds committed
1013 1014 1015
}

/*
Jens Axboe's avatar
Jens Axboe committed
1016 1017
 * 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
1018 1019 1020 1021 1022
 *
 * queue lock must be held here.
 */
static void cfq_put_queue(struct cfq_queue *cfqq)
{
1023 1024 1025
	struct cfq_data *cfqd = cfqq->cfqd;

	BUG_ON(atomic_read(&cfqq->ref) <= 0);
Linus Torvalds's avatar
Linus Torvalds committed
1026 1027 1028 1029 1030

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

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

1034
	if (unlikely(cfqd->active_queue == cfqq))
Jens Axboe's avatar
Jens Axboe committed
1035
		__cfq_slice_expired(cfqd, cfqq, 0);
1036

Linus Torvalds's avatar
Linus Torvalds committed
1037 1038 1039 1040 1041 1042 1043 1044
	/*
	 * 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
1045
static struct cfq_queue *
Jens Axboe's avatar
Jens Axboe committed
1046 1047
__cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned int prio,
		    const int hashval)
Linus Torvalds's avatar
Linus Torvalds committed
1048 1049
{
	struct hlist_head *hash_list = &cfqd->cfq_hash[hashval];
1050 1051
	struct hlist_node *entry;
	struct cfq_queue *__cfqq;
Linus Torvalds's avatar
Linus Torvalds committed
1052

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

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

	return NULL;
}

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

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

1075 1076 1077
	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);
1078
		kmem_cache_free(cfq_ioc_pool, __cic);
1079
		freed++;
Linus Torvalds's avatar
Linus Torvalds committed
1080 1081
	}

1082 1083 1084
	elv_ioc_count_mod(ioc_count, -freed);

	if (ioc_gone && !elv_ioc_count_read(ioc_count))
1085
		complete(ioc_gone);
Linus Torvalds's avatar
Linus Torvalds committed
1086 1087
}

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

1093 1094
	cfq_put_queue(cfqq);
}
1095

1096 1097 1098
static void __cfq_exit_single_io_context(struct cfq_data *cfqd,
					 struct cfq_io_context *cic)
{
1099 1100 1101 1102
	list_del_init(&cic->queue_list);
	smp_wmb();
	cic->key = NULL;