cfq-iosched.c 51.7 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
static struct kmem_cache *cfq_pool;
static struct kmem_cache *cfq_ioc_pool;
Linus Torvalds's avatar
Linus Torvalds committed
48

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
static inline pid_t cfq_queue_pid(struct task_struct *task, int rw, int is_sync)
223
{
224 225 226 227
	/*
	 * Use the per-process queue, for read requests and syncronous writes
	 */
	if (!(rw & REQ_RW) || is_sync)
228 229 230 231 232
		return task->pid;

	return CFQ_KEY_ASYNC;
}

Linus Torvalds's avatar
Linus Torvalds committed
233
/*
Jens Axboe's avatar
Jens Axboe committed
234
 * Lifted from AS - choose which of rq1 and rq2 that is best served now.
Linus Torvalds's avatar
Linus Torvalds committed
235
 * We choose the request that is closest to the head right now. Distance
236
 * behind the head is penalized and only allowed to a certain extent.
Linus Torvalds's avatar
Linus Torvalds committed
237
 */
Jens Axboe's avatar
Jens Axboe committed
238 239
static struct request *
cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2)
Linus Torvalds's avatar
Linus Torvalds committed
240 241 242
{
	sector_t last, s1, s2, d1 = 0, d2 = 0;
	unsigned long back_max;
243 244 245
#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
246

Jens Axboe's avatar
Jens Axboe committed
247 248 249 250
	if (rq1 == NULL || rq1 == rq2)
		return rq2;
	if (rq2 == NULL)
		return rq1;
251

Jens Axboe's avatar
Jens Axboe committed
252 253 254 255
	if (rq_is_sync(rq1) && !rq_is_sync(rq2))
		return rq1;
	else if (rq_is_sync(rq2) && !rq_is_sync(rq1))
		return rq2;
256 257 258 259
	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
260

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

	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
281
		wrap |= CFQ_RQ1_WRAP;
Linus Torvalds's avatar
Linus Torvalds committed
282 283 284 285 286 287

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

	/* Found required data */
291 292 293 294 295 296

	/*
	 * 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
297
	case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
298
		if (d1 < d2)
Jens Axboe's avatar
Jens Axboe committed
299
			return rq1;
300
		else if (d2 < d1)
Jens Axboe's avatar
Jens Axboe committed
301
			return rq2;
302 303
		else {
			if (s1 >= s2)
Jens Axboe's avatar
Jens Axboe committed
304
				return rq1;
305
			else
Jens Axboe's avatar
Jens Axboe committed
306
				return rq2;
307
		}
Linus Torvalds's avatar
Linus Torvalds committed
308

309
	case CFQ_RQ2_WRAP:
Jens Axboe's avatar
Jens Axboe committed
310
		return rq1;
311
	case CFQ_RQ1_WRAP:
Jens Axboe's avatar
Jens Axboe committed
312 313
		return rq2;
	case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
314 315 316 317 318 319 320 321
	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
322
			return rq1;
Linus Torvalds's avatar
Linus Torvalds committed
323
		else
Jens Axboe's avatar
Jens Axboe committed
324
			return rq2;
Linus Torvalds's avatar
Linus Torvalds committed
325 326 327 328 329 330
	}
}

/*
 * would be nice to take fifo expire time into account as well
 */
Jens Axboe's avatar
Jens Axboe committed
331 332 333
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
334
{
335 336
	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
337
	struct request *next = NULL, *prev = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
338

339
	BUG_ON(RB_EMPTY_NODE(&last->rb_node));
Linus Torvalds's avatar
Linus Torvalds committed
340 341

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

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

352
	return cfq_choose_req(cfqd, next, prev);
Linus Torvalds's avatar
Linus Torvalds committed
353 354
}

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

360 361 362 363 364
	/*
	 * Resorting requires the cfqq to be on the RR list already.
	 */
	if (!cfq_cfqq_on_rr(cfqq))
		return;
Linus Torvalds's avatar
Linus Torvalds committed
365

366
	list_del(&cfqq->cfq_list);
Linus Torvalds's avatar
Linus Torvalds committed
367

368 369 370 371 372 373 374 375 376 377 378 379
	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
380
		if (cfq_cfqq_dispatched(cfqq))
381 382 383
			list = &cfqd->busy_rr;
		else
			list = &cfqd->rr_list[cfqq->ioprio];
Linus Torvalds's avatar
Linus Torvalds committed
384 385
	}

386
	/*
387 388 389
	 * 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.
390
	 */
391 392 393
	if (preempted || cfq_cfqq_queue_new(cfqq)) {
		struct list_head *n = list;
		struct cfq_queue *__cfqq;
394

395 396 397 398
		while (n->next != list) {
			__cfqq = list_entry_cfqq(n->next);
			if (!cfq_cfqq_queue_new(__cfqq))
				break;
Linus Torvalds's avatar
Linus Torvalds committed
399

400 401
			n = n->next;
		}
Linus Torvalds's avatar
Linus Torvalds committed
402

403
		list = n;
Linus Torvalds's avatar
Linus Torvalds committed
404 405
	}

406
	list_add_tail(&cfqq->cfq_list, list);
Linus Torvalds's avatar
Linus Torvalds committed
407 408 409 410
}

/*
 * add to busy list of queues for service, trying to be fair in ordering
411
 * the pending list according to last request service
Linus Torvalds's avatar
Linus Torvalds committed
412 413
 */
static inline void
414
cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
415
{
Jens Axboe's avatar
Jens Axboe committed
416 417
	BUG_ON(cfq_cfqq_on_rr(cfqq));
	cfq_mark_cfqq_on_rr(cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
418 419
	cfqd->busy_queues++;

420
	cfq_resort_rr_list(cfqq, 0);
Linus Torvalds's avatar
Linus Torvalds committed
421 422 423 424 425
}

static inline void
cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
{
Jens Axboe's avatar
Jens Axboe committed
426 427
	BUG_ON(!cfq_cfqq_on_rr(cfqq));
	cfq_clear_cfqq_on_rr(cfqq);
428
	list_del_init(&cfqq->cfq_list);
Linus Torvalds's avatar
Linus Torvalds committed
429 430 431 432 433 434 435 436

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

/*
 * rb tree support functions
 */
Jens Axboe's avatar
Jens Axboe committed
437
static inline void cfq_del_rq_rb(struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
438
{
Jens Axboe's avatar
Jens Axboe committed
439
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
440
	struct cfq_data *cfqd = cfqq->cfqd;
Jens Axboe's avatar
Jens Axboe committed
441
	const int sync = rq_is_sync(rq);
Linus Torvalds's avatar
Linus Torvalds committed
442

443 444
	BUG_ON(!cfqq->queued[sync]);
	cfqq->queued[sync]--;
Linus Torvalds's avatar
Linus Torvalds committed
445

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

448
	if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
449
		cfq_del_cfqq_rr(cfqd, cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
450 451
}

Jens Axboe's avatar
Jens Axboe committed
452
static void cfq_add_rq_rb(struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
453
{
Jens Axboe's avatar
Jens Axboe committed
454
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
Linus Torvalds's avatar
Linus Torvalds committed
455
	struct cfq_data *cfqd = cfqq->cfqd;
456
	struct request *__alias;
Linus Torvalds's avatar
Linus Torvalds committed
457

458
	cfqq->queued[rq_is_sync(rq)]++;
Linus Torvalds's avatar
Linus Torvalds committed
459 460 461 462 463

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

	if (!cfq_cfqq_on_rr(cfqq))
		cfq_add_cfqq_rr(cfqd, cfqq);
Linus Torvalds's avatar
Linus Torvalds committed
469 470 471
}

static inline void
Jens Axboe's avatar
Jens Axboe committed
472
cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
473
{
474 475
	elv_rb_del(&cfqq->sort_list, rq);
	cfqq->queued[rq_is_sync(rq)]--;
Jens Axboe's avatar
Jens Axboe committed
476
	cfq_add_rq_rb(rq);
Linus Torvalds's avatar
Linus Torvalds committed
477 478
}

479 480
static struct request *
cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
Linus Torvalds's avatar
Linus Torvalds committed
481
{
482
	struct task_struct *tsk = current;
483
	pid_t key = cfq_queue_pid(tsk, bio_data_dir(bio), bio_sync(bio));
484
	struct cfq_queue *cfqq;
Linus Torvalds's avatar
Linus Torvalds committed
485

486
	cfqq = cfq_find_cfq_hash(cfqd, key, tsk->ioprio);
487 488 489
	if (cfqq) {
		sector_t sector = bio->bi_sector + bio_sectors(bio);

490
		return elv_rb_find(&cfqq->sort_list, sector);
491
	}
Linus Torvalds's avatar
Linus Torvalds committed
492 493 494 495

	return NULL;
}

496
static void cfq_activate_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
497
{
498
	struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe's avatar
Jens Axboe committed
499

500
	cfqd->rq_in_driver++;
501 502 503 504 505 506 507 508 509

	/*
	 * 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
510 511
}

512
static void cfq_deactivate_request(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
513
{
514 515 516 517
	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
518 519
}

520
static void cfq_remove_request(struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
521
{
Jens Axboe's avatar
Jens Axboe committed
522
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
523

Jens Axboe's avatar
Jens Axboe committed
524 525
	if (cfqq->next_rq == rq)
		cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
Linus Torvalds's avatar
Linus Torvalds committed
526

527
	list_del_init(&rq->queuelist);
Jens Axboe's avatar
Jens Axboe committed
528
	cfq_del_rq_rb(rq);
529 530 531 532 533

	if (rq_is_meta(rq)) {
		WARN_ON(!cfqq->meta_pending);
		cfqq->meta_pending--;
	}
Linus Torvalds's avatar
Linus Torvalds committed
534 535 536 537 538 539 540 541
}

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;

542
	__rq = cfq_find_rq_fmerge(cfqd, bio);
543
	if (__rq && elv_rq_merge_ok(__rq, bio)) {
544 545
		*req = __rq;
		return ELEVATOR_FRONT_MERGE;
Linus Torvalds's avatar
Linus Torvalds committed
546 547 548 549 550
	}

	return ELEVATOR_NO_MERGE;
}

551 552
static void cfq_merged_request(request_queue_t *q, struct request *req,
			       int type)
Linus Torvalds's avatar
Linus Torvalds committed
553
{
554
	if (type == ELEVATOR_FRONT_MERGE) {
Jens Axboe's avatar
Jens Axboe committed
555
		struct cfq_queue *cfqq = RQ_CFQQ(req);
Linus Torvalds's avatar
Linus Torvalds committed
556

Jens Axboe's avatar
Jens Axboe committed
557
		cfq_reposition_rq_rb(cfqq, req);
Linus Torvalds's avatar
Linus Torvalds committed
558 559 560 561 562 563 564
	}
}

static void
cfq_merged_requests(request_queue_t *q, struct request *rq,
		    struct request *next)
{
565 566 567 568 569 570 571
	/*
	 * 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);

572
	cfq_remove_request(next);
573 574
}

575 576 577 578 579 580 581 582 583
static int cfq_allow_merge(request_queue_t *q, struct request *rq,
			   struct bio *bio)
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
	const int rw = bio_data_dir(bio);
	struct cfq_queue *cfqq;
	pid_t key;

	/*
584
	 * Disallow merge of a sync bio into an async request.
585
	 */
586
	if ((bio_data_dir(bio) == READ || bio_sync(bio)) && !rq_is_sync(rq))
587 588 589
		return 0;

	/*
590 591
	 * Lookup the cfqq that this bio will be queued with. Allow
	 * merge only if rq is queued there.
592
	 */
593
	key = cfq_queue_pid(current, rw, bio_sync(bio));
594
	cfqq = cfq_find_cfq_hash(cfqd, key, current->ioprio);
595 596 597

	if (cfqq == RQ_CFQQ(rq))
		return 1;
598

599
	return 0;
600 601
}

602 603 604 605 606 607 608 609 610 611 612 613
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
614 615
		cfq_clear_cfqq_must_alloc_slice(cfqq);
		cfq_clear_cfqq_fifo_expire(cfqq);
616 617 618 619 620
	}

	cfqd->active_queue = cfqq;
}

621 622 623 624 625 626 627 628 629 630 631 632
/*
 * 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);

633
	if (!preempted && !cfq_cfqq_dispatched(cfqq))
634 635 636 637
		cfq_schedule_dispatch(cfqd);

	cfq_clear_cfqq_must_dispatch(cfqq);
	cfq_clear_cfqq_wait_request(cfqq);
638
	cfq_clear_cfqq_queue_new(cfqq);
639 640 641 642 643 644 645 646 647 648

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

649
	cfq_resort_rr_list(cfqq, preempted);
650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669

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

670 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 701 702 703
/*
 * 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
704
		}
705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721
	} 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
722 723
	}

724 725 726
	return prio;
}

Jens Axboe's avatar
Jens Axboe committed
727
static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd)
728
{
729
	struct cfq_queue *cfqq = NULL;
730

731 732 733 734 735 736
	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
		 */
737
		cfqq = list_entry_cfqq(cfqd->cur_rr.next);
738 739 740 741 742
	} 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.
		 */
743
		cfqq = list_entry_cfqq(cfqd->busy_rr.next);
744 745 746 747 748 749
	} 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
		 */
750 751 752 753 754 755 756 757 758
		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
759
	return cfqq;
760 761
}

762 763
#define CIC_SEEKY(cic) ((cic)->seek_mean > (128 * 1024))

764 765 766
static int cfq_arm_slice_timer(struct cfq_data *cfqd, struct cfq_queue *cfqq)

{
767
	struct cfq_io_context *cic;
768 769
	unsigned long sl;

770
	WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
771 772 773 774 775 776 777
	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
778
	if (!cfq_cfqq_idle_window(cfqq))
779 780 781 782
		return 0;
	/*
	 * task has exited, don't wait
	 */
783 784
	cic = cfqd->active_cic;
	if (!cic || !cic->ioc->task)
785 786
		return 0;

Jens Axboe's avatar
Jens Axboe committed
787 788
	cfq_mark_cfqq_must_dispatch(cfqq);
	cfq_mark_cfqq_wait_request(cfqq);
789

790
	sl = min(cfqq->slice_end - 1, (unsigned long) cfqd->cfq_slice_idle);
791 792 793 794 795 796

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

800
	mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
801
	return 1;
Linus Torvalds's avatar
Linus Torvalds committed
802 803
}

Jens Axboe's avatar
Jens Axboe committed
804
static void cfq_dispatch_insert(request_queue_t *q, struct request *rq)
Linus Torvalds's avatar
Linus Torvalds committed
805 806
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
Jens Axboe's avatar
Jens Axboe committed
807
	struct cfq_queue *cfqq = RQ_CFQQ(rq);
808

809 810 811
	cfq_remove_request(rq);
	cfqq->on_dispatch[rq_is_sync(rq)]++;
	elv_dispatch_sort(q, rq);
812 813 814

	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
815 816 817 818 819
}

/*
 * return expired entry, or NULL to just start from scratch in rbtree
 */
Jens Axboe's avatar
Jens Axboe committed
820
static inline struct request *cfq_check_fifo(struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
821 822
{
	struct cfq_data *cfqd = cfqq->cfqd;
823
	struct request *rq;
824
	int fifo;
Linus Torvalds's avatar
Linus Torvalds committed
825

Jens Axboe's avatar
Jens Axboe committed
826
	if (cfq_cfqq_fifo_expire(cfqq))
Linus Torvalds's avatar
Linus Torvalds committed
827
		return NULL;
828 829
	if (list_empty(&cfqq->fifo))
		return NULL;
Linus Torvalds's avatar
Linus Torvalds committed
830

831 832
	fifo = cfq_cfqq_class_sync(cfqq);
	rq = rq_entry_fifo(cfqq->fifo.next);
Linus Torvalds's avatar
Linus Torvalds committed
833

834 835 836
	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
837 838 839 840 841 842
	}

	return NULL;
}

/*
Jens Axboe's avatar
Jens Axboe committed
843 844 845
 * 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
846
 */
847 848 849 850 851 852 853 854 855 856
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
857
static inline void
858
cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
Linus Torvalds's avatar
Linus Torvalds committed
859
{
860 861
	cfqq->slice_end = cfq_prio_to_slice(cfqd, cfqq) + jiffies;
}
Linus Torvalds's avatar
Linus Torvalds committed
862

863 864 865 866
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
867

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

870
	return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
Linus Torvalds's avatar
Linus Torvalds committed
871 872
}

873 874 875
/*
 * get next queue for service
 */
876
static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
Linus Torvalds's avatar
Linus Torvalds committed
877
{
878
	unsigned long now = jiffies;
Linus Torvalds's avatar
Linus Torvalds committed
879 880
	struct cfq_queue *cfqq;

881 882 883
	cfqq = cfqd->active_queue;
	if (!cfqq)
		goto new_queue;
Linus Torvalds's avatar
Linus Torvalds committed
884

885 886 887
	/*
	 * slice has expired
	 */
Jens Axboe's avatar
Jens Axboe committed
888 889
	if (!cfq_cfqq_must_dispatch(cfqq) && time_after(now, cfqq->slice_end))
		goto expire;
Linus Torvalds's avatar
Linus Torvalds committed
890

891 892 893 894
	/*
	 * if queue has requests, dispatch one. if not, check if
	 * enough slice is left to wait for one
	 */
895
	if (!RB_EMPTY_ROOT(&cfqq->sort_list))
896
		goto keep_queue;
897 898 899 900
	else if (cfq_cfqq_dispatched(cfqq)) {
		cfqq = NULL;
		goto keep_queue;
	} else if (cfq_cfqq_class_sync(cfqq)) {
901 902 903 904
		if (cfq_arm_slice_timer(cfqd, cfqq))
			return NULL;
	}

Jens Axboe's avatar
Jens Axboe committed
905
expire:
906
	cfq_slice_expired(cfqd, 0);
Jens Axboe's avatar
Jens Axboe committed
907 908
new_queue:
	cfqq = cfq_set_active_queue(cfqd);
909
keep_queue:
Jens Axboe's avatar
Jens Axboe committed
910
	return cfqq;
911 912 913 914 915 916 917 918
}

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

919
	BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
920 921

	do {
Jens Axboe's avatar
Jens Axboe committed
922
		struct request *rq;
Linus Torvalds's avatar
Linus Torvalds committed
923 924

		/*
925
		 * follow expired path, else get first next available
Linus Torvalds's avatar
Linus Torvalds committed
926
		 */
Jens Axboe's avatar
Jens Axboe committed
927 928
		if ((rq = cfq_check_fifo(cfqq)) == NULL)
			rq = cfqq->next_rq;
929 930 931 932

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

935 936
		cfqd->dispatch_slice++;
		dispatched++;
Linus Torvalds's avatar
Linus Torvalds committed
937

938
		if (!cfqd->active_cic) {
Jens Axboe's avatar
Jens Axboe committed
939 940
			atomic_inc(&RQ_CIC(rq)->ioc->refcount);
			cfqd->active_cic = RQ_CIC(rq);
941
		}
Linus Torvalds's avatar
Linus Torvalds committed
942

943
		if (RB_EMPTY_ROOT(&cfqq->sort_list))
944 945 946 947 948
			break;

	} while (dispatched < max_dispatch);

	/*
949
	 * if slice end isn't set yet, set it.
950 951 952 953 954 955 956 957 958 959
	 */
	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)) ||
960 961
	    cfq_class_idle(cfqq) ||
	    !cfq_cfqq_idle_window(cfqq))
962 963 964 965 966
		cfq_slice_expired(cfqd, 0);

	return dispatched;
}

967 968 969 970
static int
cfq_forced_dispatch_cfqqs(struct list_head *list)
{
	struct cfq_queue *cfqq, *next;
971
	int dispatched;
972

973
	dispatched = 0;
974
	list_for_each_entry_safe(cfqq, next, list, cfq_list) {
Jens Axboe's avatar
Jens Axboe committed
975 976
		while (cfqq->next_rq) {
			cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
977 978 979 980
			dispatched++;
		}
		BUG_ON(!list_empty(&cfqq->fifo));
	}
981

982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003
	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;
}

1004
static int
1005
cfq_dispatch_requests(request_queue_t *q, int force)
1006 1007
{
	struct cfq_data *cfqd = q->elevator->elevator_data;
1008 1009
	struct cfq_queue *cfqq, *prev_cfqq;
	int dispatched;
1010 1011 1012 1013

	if (!cfqd->busy_queues)
		return 0;

1014 1015 1016
	if (unlikely(force))
		return cfq_forced_dispatch(cfqd);

1017 1018 1019
	dispatched = 0;
	prev_cfqq = NULL;
	while ((cfqq = cfq_select_queue(cfqd)) != NULL) {
1020 1021
		int max_dispatch;

1022 1023 1024 1025 1026 1027
		/*
		 * Don't repeat dispatch from the previous queue.
		 */
		if (prev_cfqq == cfqq)
			break;

Jens Axboe's avatar
Jens Axboe committed
1028 1029
		cfq_clear_cfqq_must_dispatch(cfqq);
		cfq_clear_cfqq_wait_request(cfqq);
1030 1031
		del_timer(&cfqd->idle_slice_timer);

1032 1033 1034
		max_dispatch = cfqd->cfq_quantum;
		if (cfq_class_idle(cfqq))
			max_dispatch = 1;
Linus Torvalds's avatar
Linus Torvalds committed
1035

1036 1037 1038 1039 1040 1041 1042 1043 1044 1045
		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
1046 1047
	}

1048
	return dispatched;
Linus Torvalds's avatar
Linus Torvalds committed
1049 1050 1051
}

/*
Jens Axboe's avatar
Jens Axboe committed
1052 1053
 * 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
1054 1055 1056 1057 1058
 *
 * queue lock must be held here.
 */
static void cfq_put_queue(struct cfq_queue *cfqq)
{
1059 1060 1061
	struct cfq_data *cfqd = cfqq->cfqd;

	BUG_ON(atomic_read(&cfqq->ref) <= 0);
Linus Torvalds's avatar
Linus Torvalds committed
1062 1063 1064 1065 1066

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

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

1070
	if (unlikely(cfqd->active_queue == cfqq))
Jens Axboe's avatar
Jens Axboe committed
1071
		__cfq_slice_expired(cfqd, cfqq, 0);
1072

Linus Torvalds's avatar
Linus Torvalds committed
1073 1074 1075 1076 1077 1078 1079 1080
	/*
	 * 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
1081
static struct cfq_queue *
Jens Axboe's avatar
Jens Axboe committed
1082 1083
__cfq_find_cfq_hash(struct cfq_data *cfqd, unsigned int key, unsigned int prio,
		    const int hashval)
Linus Torvalds's avatar
Linus Torvalds committed
1084 1085
{
	struct hlist_head *hash_list = &cfqd->cfq_hash[hashval];
1086 1087
	struct hlist_node *entry;
	struct cfq_queue *__cfqq;
Linus Torvalds's avatar
Linus Torvalds committed
1088

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

1092
		if (__cfqq->key == key && (__p == prio || !prio))
Linus Torvalds's avatar
Linus Torvalds committed
1093 1094 1095 1096 1097 1098 1099
			return __cfqq;
	}

	return NULL;
}

static struct cfq_queue *