blkio: Drop the reference to queue once the task changes cgroup
[linux-2.6.git] / block / cfq-iosched.c
1 /*
2  *  CFQ, or complete fairness queueing, disk scheduler.
3  *
4  *  Based on ideas from a previously unfinished io
5  *  scheduler (round robin per-process disk scheduling) and Andrea Arcangeli.
6  *
7  *  Copyright (C) 2003 Jens Axboe <axboe@kernel.dk>
8  */
9 #include <linux/module.h>
10 #include <linux/blkdev.h>
11 #include <linux/elevator.h>
12 #include <linux/jiffies.h>
13 #include <linux/rbtree.h>
14 #include <linux/ioprio.h>
15 #include <linux/blktrace_api.h>
16 #include "blk-cgroup.h"
17
18 /*
19  * tunables
20  */
21 /* max queue in one round of service */
22 static const int cfq_quantum = 4;
23 static const int cfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
24 /* maximum backwards seek, in KiB */
25 static const int cfq_back_max = 16 * 1024;
26 /* penalty of a backwards seek */
27 static const int cfq_back_penalty = 2;
28 static const int cfq_slice_sync = HZ / 10;
29 static int cfq_slice_async = HZ / 25;
30 static const int cfq_slice_async_rq = 2;
31 static int cfq_slice_idle = HZ / 125;
32 static const int cfq_target_latency = HZ * 3/10; /* 300 ms */
33 static const int cfq_hist_divisor = 4;
34
35 /*
36  * offset from end of service tree
37  */
38 #define CFQ_IDLE_DELAY          (HZ / 5)
39
40 /*
41  * below this threshold, we consider thinktime immediate
42  */
43 #define CFQ_MIN_TT              (2)
44
45 /*
46  * Allow merged cfqqs to perform this amount of seeky I/O before
47  * deciding to break the queues up again.
48  */
49 #define CFQQ_COOP_TOUT          (HZ)
50
51 #define CFQ_SLICE_SCALE         (5)
52 #define CFQ_HW_QUEUE_MIN        (5)
53 #define CFQ_SERVICE_SHIFT       12
54
55 #define RQ_CIC(rq)              \
56         ((struct cfq_io_context *) (rq)->elevator_private)
57 #define RQ_CFQQ(rq)             (struct cfq_queue *) ((rq)->elevator_private2)
58
59 static struct kmem_cache *cfq_pool;
60 static struct kmem_cache *cfq_ioc_pool;
61
62 static DEFINE_PER_CPU(unsigned long, cfq_ioc_count);
63 static struct completion *ioc_gone;
64 static DEFINE_SPINLOCK(ioc_gone_lock);
65
66 #define CFQ_PRIO_LISTS          IOPRIO_BE_NR
67 #define cfq_class_idle(cfqq)    ((cfqq)->ioprio_class == IOPRIO_CLASS_IDLE)
68 #define cfq_class_rt(cfqq)      ((cfqq)->ioprio_class == IOPRIO_CLASS_RT)
69
70 #define sample_valid(samples)   ((samples) > 80)
71 #define rb_entry_cfqg(node)     rb_entry((node), struct cfq_group, rb_node)
72
73 /*
74  * Most of our rbtree usage is for sorting with min extraction, so
75  * if we cache the leftmost node we don't have to walk down the tree
76  * to find it. Idea borrowed from Ingo Molnars CFS scheduler. We should
77  * move this into the elevator for the rq sorting as well.
78  */
79 struct cfq_rb_root {
80         struct rb_root rb;
81         struct rb_node *left;
82         unsigned count;
83         u64 min_vdisktime;
84         struct rb_node *active;
85         unsigned total_weight;
86 };
87 #define CFQ_RB_ROOT     (struct cfq_rb_root) { RB_ROOT, NULL, 0, 0, }
88
89 /*
90  * Per process-grouping structure
91  */
92 struct cfq_queue {
93         /* reference count */
94         atomic_t ref;
95         /* various state flags, see below */
96         unsigned int flags;
97         /* parent cfq_data */
98         struct cfq_data *cfqd;
99         /* service_tree member */
100         struct rb_node rb_node;
101         /* service_tree key */
102         unsigned long rb_key;
103         /* prio tree member */
104         struct rb_node p_node;
105         /* prio tree root we belong to, if any */
106         struct rb_root *p_root;
107         /* sorted list of pending requests */
108         struct rb_root sort_list;
109         /* if fifo isn't expired, next request to serve */
110         struct request *next_rq;
111         /* requests queued in sort_list */
112         int queued[2];
113         /* currently allocated requests */
114         int allocated[2];
115         /* fifo list of requests in sort_list */
116         struct list_head fifo;
117
118         /* time when queue got scheduled in to dispatch first request. */
119         unsigned long dispatch_start;
120         /* time when first request from queue completed and slice started. */
121         unsigned long slice_start;
122         unsigned long slice_end;
123         long slice_resid;
124         unsigned int slice_dispatch;
125
126         /* pending metadata requests */
127         int meta_pending;
128         /* number of requests that are on the dispatch list or inside driver */
129         int dispatched;
130
131         /* io prio of this group */
132         unsigned short ioprio, org_ioprio;
133         unsigned short ioprio_class, org_ioprio_class;
134
135         unsigned int seek_samples;
136         u64 seek_total;
137         sector_t seek_mean;
138         sector_t last_request_pos;
139         unsigned long seeky_start;
140
141         pid_t pid;
142
143         struct cfq_rb_root *service_tree;
144         struct cfq_queue *new_cfqq;
145         struct cfq_group *cfqg;
146         /* Sectors dispatched in current dispatch round */
147         unsigned long nr_sectors;
148 };
149
150 /*
151  * First index in the service_trees.
152  * IDLE is handled separately, so it has negative index
153  */
154 enum wl_prio_t {
155         BE_WORKLOAD = 0,
156         RT_WORKLOAD = 1,
157         IDLE_WORKLOAD = 2,
158 };
159
160 /*
161  * Second index in the service_trees.
162  */
163 enum wl_type_t {
164         ASYNC_WORKLOAD = 0,
165         SYNC_NOIDLE_WORKLOAD = 1,
166         SYNC_WORKLOAD = 2
167 };
168
169 /* This is per cgroup per device grouping structure */
170 struct cfq_group {
171         /* group service_tree member */
172         struct rb_node rb_node;
173
174         /* group service_tree key */
175         u64 vdisktime;
176         unsigned int weight;
177         bool on_st;
178
179         /* number of cfqq currently on this group */
180         int nr_cfqq;
181
182         /* Per group busy queus average. Useful for workload slice calc. */
183         unsigned int busy_queues_avg[2];
184         /*
185          * rr lists of queues with requests, onle rr for each priority class.
186          * Counts are embedded in the cfq_rb_root
187          */
188         struct cfq_rb_root service_trees[2][3];
189         struct cfq_rb_root service_tree_idle;
190
191         unsigned long saved_workload_slice;
192         enum wl_type_t saved_workload;
193         enum wl_prio_t saved_serving_prio;
194         struct blkio_group blkg;
195 #ifdef CONFIG_CFQ_GROUP_IOSCHED
196         struct hlist_node cfqd_node;
197         atomic_t ref;
198 #endif
199 };
200
201 /*
202  * Per block device queue structure
203  */
204 struct cfq_data {
205         struct request_queue *queue;
206         /* Root service tree for cfq_groups */
207         struct cfq_rb_root grp_service_tree;
208         struct cfq_group root_group;
209         /* Number of active cfq groups on group service tree */
210         int nr_groups;
211
212         /*
213          * The priority currently being served
214          */
215         enum wl_prio_t serving_prio;
216         enum wl_type_t serving_type;
217         unsigned long workload_expires;
218         struct cfq_group *serving_group;
219         bool noidle_tree_requires_idle;
220
221         /*
222          * Each priority tree is sorted by next_request position.  These
223          * trees are used when determining if two or more queues are
224          * interleaving requests (see cfq_close_cooperator).
225          */
226         struct rb_root prio_trees[CFQ_PRIO_LISTS];
227
228         unsigned int busy_queues;
229
230         int rq_in_driver[2];
231         int sync_flight;
232
233         /*
234          * queue-depth detection
235          */
236         int rq_queued;
237         int hw_tag;
238         /*
239          * hw_tag can be
240          * -1 => indeterminate, (cfq will behave as if NCQ is present, to allow better detection)
241          *  1 => NCQ is present (hw_tag_est_depth is the estimated max depth)
242          *  0 => no NCQ
243          */
244         int hw_tag_est_depth;
245         unsigned int hw_tag_samples;
246
247         /*
248          * idle window management
249          */
250         struct timer_list idle_slice_timer;
251         struct work_struct unplug_work;
252
253         struct cfq_queue *active_queue;
254         struct cfq_io_context *active_cic;
255
256         /*
257          * async queue for each priority case
258          */
259         struct cfq_queue *async_cfqq[2][IOPRIO_BE_NR];
260         struct cfq_queue *async_idle_cfqq;
261
262         sector_t last_position;
263
264         /*
265          * tunables, see top of file
266          */
267         unsigned int cfq_quantum;
268         unsigned int cfq_fifo_expire[2];
269         unsigned int cfq_back_penalty;
270         unsigned int cfq_back_max;
271         unsigned int cfq_slice[2];
272         unsigned int cfq_slice_async_rq;
273         unsigned int cfq_slice_idle;
274         unsigned int cfq_latency;
275
276         struct list_head cic_list;
277
278         /*
279          * Fallback dummy cfqq for extreme OOM conditions
280          */
281         struct cfq_queue oom_cfqq;
282
283         unsigned long last_end_sync_rq;
284
285         /* List of cfq groups being managed on this device*/
286         struct hlist_head cfqg_list;
287 };
288
289 static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd);
290
291 static struct cfq_rb_root *service_tree_for(struct cfq_group *cfqg,
292                                             enum wl_prio_t prio,
293                                             enum wl_type_t type,
294                                             struct cfq_data *cfqd)
295 {
296         if (!cfqg)
297                 return NULL;
298
299         if (prio == IDLE_WORKLOAD)
300                 return &cfqg->service_tree_idle;
301
302         return &cfqg->service_trees[prio][type];
303 }
304
305 enum cfqq_state_flags {
306         CFQ_CFQQ_FLAG_on_rr = 0,        /* on round-robin busy list */
307         CFQ_CFQQ_FLAG_wait_request,     /* waiting for a request */
308         CFQ_CFQQ_FLAG_must_dispatch,    /* must be allowed a dispatch */
309         CFQ_CFQQ_FLAG_must_alloc_slice, /* per-slice must_alloc flag */
310         CFQ_CFQQ_FLAG_fifo_expire,      /* FIFO checked in this slice */
311         CFQ_CFQQ_FLAG_idle_window,      /* slice idling enabled */
312         CFQ_CFQQ_FLAG_prio_changed,     /* task priority has changed */
313         CFQ_CFQQ_FLAG_slice_new,        /* no requests dispatched in slice */
314         CFQ_CFQQ_FLAG_sync,             /* synchronous queue */
315         CFQ_CFQQ_FLAG_coop,             /* cfqq is shared */
316         CFQ_CFQQ_FLAG_deep,             /* sync cfqq experienced large depth */
317 };
318
319 #define CFQ_CFQQ_FNS(name)                                              \
320 static inline void cfq_mark_cfqq_##name(struct cfq_queue *cfqq)         \
321 {                                                                       \
322         (cfqq)->flags |= (1 << CFQ_CFQQ_FLAG_##name);                   \
323 }                                                                       \
324 static inline void cfq_clear_cfqq_##name(struct cfq_queue *cfqq)        \
325 {                                                                       \
326         (cfqq)->flags &= ~(1 << CFQ_CFQQ_FLAG_##name);                  \
327 }                                                                       \
328 static inline int cfq_cfqq_##name(const struct cfq_queue *cfqq)         \
329 {                                                                       \
330         return ((cfqq)->flags & (1 << CFQ_CFQQ_FLAG_##name)) != 0;      \
331 }
332
333 CFQ_CFQQ_FNS(on_rr);
334 CFQ_CFQQ_FNS(wait_request);
335 CFQ_CFQQ_FNS(must_dispatch);
336 CFQ_CFQQ_FNS(must_alloc_slice);
337 CFQ_CFQQ_FNS(fifo_expire);
338 CFQ_CFQQ_FNS(idle_window);
339 CFQ_CFQQ_FNS(prio_changed);
340 CFQ_CFQQ_FNS(slice_new);
341 CFQ_CFQQ_FNS(sync);
342 CFQ_CFQQ_FNS(coop);
343 CFQ_CFQQ_FNS(deep);
344 #undef CFQ_CFQQ_FNS
345
346 #ifdef CONFIG_DEBUG_CFQ_IOSCHED
347 #define cfq_log_cfqq(cfqd, cfqq, fmt, args...)  \
348         blk_add_trace_msg((cfqd)->queue, "cfq%d%c %s " fmt, (cfqq)->pid, \
349                         cfq_cfqq_sync((cfqq)) ? 'S' : 'A', \
350                         blkg_path(&(cfqq)->cfqg->blkg), ##args);
351
352 #define cfq_log_cfqg(cfqd, cfqg, fmt, args...)                          \
353         blk_add_trace_msg((cfqd)->queue, "%s " fmt,                     \
354                                 blkg_path(&(cfqg)->blkg), ##args);      \
355
356 #else
357 #define cfq_log_cfqq(cfqd, cfqq, fmt, args...)  \
358         blk_add_trace_msg((cfqd)->queue, "cfq%d " fmt, (cfqq)->pid, ##args)
359 #define cfq_log_cfqg(cfqd, cfqg, fmt, args...)          do {} while (0);
360 #endif
361 #define cfq_log(cfqd, fmt, args...)     \
362         blk_add_trace_msg((cfqd)->queue, "cfq " fmt, ##args)
363
364 /* Traverses through cfq group service trees */
365 #define for_each_cfqg_st(cfqg, i, j, st) \
366         for (i = 0; i <= IDLE_WORKLOAD; i++) \
367                 for (j = 0, st = i < IDLE_WORKLOAD ? &cfqg->service_trees[i][j]\
368                         : &cfqg->service_tree_idle; \
369                         (i < IDLE_WORKLOAD && j <= SYNC_WORKLOAD) || \
370                         (i == IDLE_WORKLOAD && j == 0); \
371                         j++, st = i < IDLE_WORKLOAD ? \
372                         &cfqg->service_trees[i][j]: NULL) \
373
374
375 static inline enum wl_prio_t cfqq_prio(struct cfq_queue *cfqq)
376 {
377         if (cfq_class_idle(cfqq))
378                 return IDLE_WORKLOAD;
379         if (cfq_class_rt(cfqq))
380                 return RT_WORKLOAD;
381         return BE_WORKLOAD;
382 }
383
384
385 static enum wl_type_t cfqq_type(struct cfq_queue *cfqq)
386 {
387         if (!cfq_cfqq_sync(cfqq))
388                 return ASYNC_WORKLOAD;
389         if (!cfq_cfqq_idle_window(cfqq))
390                 return SYNC_NOIDLE_WORKLOAD;
391         return SYNC_WORKLOAD;
392 }
393
394 static inline int cfq_group_busy_queues_wl(enum wl_prio_t wl,
395                                         struct cfq_data *cfqd,
396                                         struct cfq_group *cfqg)
397 {
398         if (wl == IDLE_WORKLOAD)
399                 return cfqg->service_tree_idle.count;
400
401         return cfqg->service_trees[wl][ASYNC_WORKLOAD].count
402                 + cfqg->service_trees[wl][SYNC_NOIDLE_WORKLOAD].count
403                 + cfqg->service_trees[wl][SYNC_WORKLOAD].count;
404 }
405
406 static void cfq_dispatch_insert(struct request_queue *, struct request *);
407 static struct cfq_queue *cfq_get_queue(struct cfq_data *, bool,
408                                        struct io_context *, gfp_t);
409 static struct cfq_io_context *cfq_cic_lookup(struct cfq_data *,
410                                                 struct io_context *);
411
412 static inline int rq_in_driver(struct cfq_data *cfqd)
413 {
414         return cfqd->rq_in_driver[0] + cfqd->rq_in_driver[1];
415 }
416
417 static inline struct cfq_queue *cic_to_cfqq(struct cfq_io_context *cic,
418                                             bool is_sync)
419 {
420         return cic->cfqq[is_sync];
421 }
422
423 static inline void cic_set_cfqq(struct cfq_io_context *cic,
424                                 struct cfq_queue *cfqq, bool is_sync)
425 {
426         cic->cfqq[is_sync] = cfqq;
427 }
428
429 /*
430  * We regard a request as SYNC, if it's either a read or has the SYNC bit
431  * set (in which case it could also be direct WRITE).
432  */
433 static inline bool cfq_bio_sync(struct bio *bio)
434 {
435         return bio_data_dir(bio) == READ || bio_rw_flagged(bio, BIO_RW_SYNCIO);
436 }
437
438 /*
439  * scheduler run of queue, if there are requests pending and no one in the
440  * driver that will restart queueing
441  */
442 static inline void cfq_schedule_dispatch(struct cfq_data *cfqd)
443 {
444         if (cfqd->busy_queues) {
445                 cfq_log(cfqd, "schedule dispatch");
446                 kblockd_schedule_work(cfqd->queue, &cfqd->unplug_work);
447         }
448 }
449
450 static int cfq_queue_empty(struct request_queue *q)
451 {
452         struct cfq_data *cfqd = q->elevator->elevator_data;
453
454         return !cfqd->rq_queued;
455 }
456
457 /*
458  * Scale schedule slice based on io priority. Use the sync time slice only
459  * if a queue is marked sync and has sync io queued. A sync queue with async
460  * io only, should not get full sync slice length.
461  */
462 static inline int cfq_prio_slice(struct cfq_data *cfqd, bool sync,
463                                  unsigned short prio)
464 {
465         const int base_slice = cfqd->cfq_slice[sync];
466
467         WARN_ON(prio >= IOPRIO_BE_NR);
468
469         return base_slice + (base_slice/CFQ_SLICE_SCALE * (4 - prio));
470 }
471
472 static inline int
473 cfq_prio_to_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
474 {
475         return cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio);
476 }
477
478 static inline u64 cfq_scale_slice(unsigned long delta, struct cfq_group *cfqg)
479 {
480         u64 d = delta << CFQ_SERVICE_SHIFT;
481
482         d = d * BLKIO_WEIGHT_DEFAULT;
483         do_div(d, cfqg->weight);
484         return d;
485 }
486
487 static inline u64 max_vdisktime(u64 min_vdisktime, u64 vdisktime)
488 {
489         s64 delta = (s64)(vdisktime - min_vdisktime);
490         if (delta > 0)
491                 min_vdisktime = vdisktime;
492
493         return min_vdisktime;
494 }
495
496 static inline u64 min_vdisktime(u64 min_vdisktime, u64 vdisktime)
497 {
498         s64 delta = (s64)(vdisktime - min_vdisktime);
499         if (delta < 0)
500                 min_vdisktime = vdisktime;
501
502         return min_vdisktime;
503 }
504
505 static void update_min_vdisktime(struct cfq_rb_root *st)
506 {
507         u64 vdisktime = st->min_vdisktime;
508         struct cfq_group *cfqg;
509
510         if (st->active) {
511                 cfqg = rb_entry_cfqg(st->active);
512                 vdisktime = cfqg->vdisktime;
513         }
514
515         if (st->left) {
516                 cfqg = rb_entry_cfqg(st->left);
517                 vdisktime = min_vdisktime(vdisktime, cfqg->vdisktime);
518         }
519
520         st->min_vdisktime = max_vdisktime(st->min_vdisktime, vdisktime);
521 }
522
523 /*
524  * get averaged number of queues of RT/BE priority.
525  * average is updated, with a formula that gives more weight to higher numbers,
526  * to quickly follows sudden increases and decrease slowly
527  */
528
529 static inline unsigned cfq_group_get_avg_queues(struct cfq_data *cfqd,
530                                         struct cfq_group *cfqg, bool rt)
531 {
532         unsigned min_q, max_q;
533         unsigned mult  = cfq_hist_divisor - 1;
534         unsigned round = cfq_hist_divisor / 2;
535         unsigned busy = cfq_group_busy_queues_wl(rt, cfqd, cfqg);
536
537         min_q = min(cfqg->busy_queues_avg[rt], busy);
538         max_q = max(cfqg->busy_queues_avg[rt], busy);
539         cfqg->busy_queues_avg[rt] = (mult * max_q + min_q + round) /
540                 cfq_hist_divisor;
541         return cfqg->busy_queues_avg[rt];
542 }
543
544 static inline unsigned
545 cfq_group_slice(struct cfq_data *cfqd, struct cfq_group *cfqg)
546 {
547         struct cfq_rb_root *st = &cfqd->grp_service_tree;
548
549         return cfq_target_latency * cfqg->weight / st->total_weight;
550 }
551
552 static inline void
553 cfq_set_prio_slice(struct cfq_data *cfqd, struct cfq_queue *cfqq)
554 {
555         unsigned slice = cfq_prio_to_slice(cfqd, cfqq);
556         if (cfqd->cfq_latency) {
557                 /*
558                  * interested queues (we consider only the ones with the same
559                  * priority class in the cfq group)
560                  */
561                 unsigned iq = cfq_group_get_avg_queues(cfqd, cfqq->cfqg,
562                                                 cfq_class_rt(cfqq));
563                 unsigned sync_slice = cfqd->cfq_slice[1];
564                 unsigned expect_latency = sync_slice * iq;
565                 unsigned group_slice = cfq_group_slice(cfqd, cfqq->cfqg);
566
567                 if (expect_latency > group_slice) {
568                         unsigned base_low_slice = 2 * cfqd->cfq_slice_idle;
569                         /* scale low_slice according to IO priority
570                          * and sync vs async */
571                         unsigned low_slice =
572                                 min(slice, base_low_slice * slice / sync_slice);
573                         /* the adapted slice value is scaled to fit all iqs
574                          * into the target latency */
575                         slice = max(slice * group_slice / expect_latency,
576                                     low_slice);
577                 }
578         }
579         cfqq->slice_start = jiffies;
580         cfqq->slice_end = jiffies + slice;
581         cfq_log_cfqq(cfqd, cfqq, "set_slice=%lu", cfqq->slice_end - jiffies);
582 }
583
584 /*
585  * We need to wrap this check in cfq_cfqq_slice_new(), since ->slice_end
586  * isn't valid until the first request from the dispatch is activated
587  * and the slice time set.
588  */
589 static inline bool cfq_slice_used(struct cfq_queue *cfqq)
590 {
591         if (cfq_cfqq_slice_new(cfqq))
592                 return 0;
593         if (time_before(jiffies, cfqq->slice_end))
594                 return 0;
595
596         return 1;
597 }
598
599 /*
600  * Lifted from AS - choose which of rq1 and rq2 that is best served now.
601  * We choose the request that is closest to the head right now. Distance
602  * behind the head is penalized and only allowed to a certain extent.
603  */
604 static struct request *
605 cfq_choose_req(struct cfq_data *cfqd, struct request *rq1, struct request *rq2, sector_t last)
606 {
607         sector_t s1, s2, d1 = 0, d2 = 0;
608         unsigned long back_max;
609 #define CFQ_RQ1_WRAP    0x01 /* request 1 wraps */
610 #define CFQ_RQ2_WRAP    0x02 /* request 2 wraps */
611         unsigned wrap = 0; /* bit mask: requests behind the disk head? */
612
613         if (rq1 == NULL || rq1 == rq2)
614                 return rq2;
615         if (rq2 == NULL)
616                 return rq1;
617
618         if (rq_is_sync(rq1) && !rq_is_sync(rq2))
619                 return rq1;
620         else if (rq_is_sync(rq2) && !rq_is_sync(rq1))
621                 return rq2;
622         if (rq_is_meta(rq1) && !rq_is_meta(rq2))
623                 return rq1;
624         else if (rq_is_meta(rq2) && !rq_is_meta(rq1))
625                 return rq2;
626
627         s1 = blk_rq_pos(rq1);
628         s2 = blk_rq_pos(rq2);
629
630         /*
631          * by definition, 1KiB is 2 sectors
632          */
633         back_max = cfqd->cfq_back_max * 2;
634
635         /*
636          * Strict one way elevator _except_ in the case where we allow
637          * short backward seeks which are biased as twice the cost of a
638          * similar forward seek.
639          */
640         if (s1 >= last)
641                 d1 = s1 - last;
642         else if (s1 + back_max >= last)
643                 d1 = (last - s1) * cfqd->cfq_back_penalty;
644         else
645                 wrap |= CFQ_RQ1_WRAP;
646
647         if (s2 >= last)
648                 d2 = s2 - last;
649         else if (s2 + back_max >= last)
650                 d2 = (last - s2) * cfqd->cfq_back_penalty;
651         else
652                 wrap |= CFQ_RQ2_WRAP;
653
654         /* Found required data */
655
656         /*
657          * By doing switch() on the bit mask "wrap" we avoid having to
658          * check two variables for all permutations: --> faster!
659          */
660         switch (wrap) {
661         case 0: /* common case for CFQ: rq1 and rq2 not wrapped */
662                 if (d1 < d2)
663                         return rq1;
664                 else if (d2 < d1)
665                         return rq2;
666                 else {
667                         if (s1 >= s2)
668                                 return rq1;
669                         else
670                                 return rq2;
671                 }
672
673         case CFQ_RQ2_WRAP:
674                 return rq1;
675         case CFQ_RQ1_WRAP:
676                 return rq2;
677         case (CFQ_RQ1_WRAP|CFQ_RQ2_WRAP): /* both rqs wrapped */
678         default:
679                 /*
680                  * Since both rqs are wrapped,
681                  * start with the one that's further behind head
682                  * (--> only *one* back seek required),
683                  * since back seek takes more time than forward.
684                  */
685                 if (s1 <= s2)
686                         return rq1;
687                 else
688                         return rq2;
689         }
690 }
691
692 /*
693  * The below is leftmost cache rbtree addon
694  */
695 static struct cfq_queue *cfq_rb_first(struct cfq_rb_root *root)
696 {
697         /* Service tree is empty */
698         if (!root->count)
699                 return NULL;
700
701         if (!root->left)
702                 root->left = rb_first(&root->rb);
703
704         if (root->left)
705                 return rb_entry(root->left, struct cfq_queue, rb_node);
706
707         return NULL;
708 }
709
710 static struct cfq_group *cfq_rb_first_group(struct cfq_rb_root *root)
711 {
712         if (!root->left)
713                 root->left = rb_first(&root->rb);
714
715         if (root->left)
716                 return rb_entry_cfqg(root->left);
717
718         return NULL;
719 }
720
721 static void rb_erase_init(struct rb_node *n, struct rb_root *root)
722 {
723         rb_erase(n, root);
724         RB_CLEAR_NODE(n);
725 }
726
727 static void cfq_rb_erase(struct rb_node *n, struct cfq_rb_root *root)
728 {
729         if (root->left == n)
730                 root->left = NULL;
731         rb_erase_init(n, &root->rb);
732         --root->count;
733 }
734
735 /*
736  * would be nice to take fifo expire time into account as well
737  */
738 static struct request *
739 cfq_find_next_rq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
740                   struct request *last)
741 {
742         struct rb_node *rbnext = rb_next(&last->rb_node);
743         struct rb_node *rbprev = rb_prev(&last->rb_node);
744         struct request *next = NULL, *prev = NULL;
745
746         BUG_ON(RB_EMPTY_NODE(&last->rb_node));
747
748         if (rbprev)
749                 prev = rb_entry_rq(rbprev);
750
751         if (rbnext)
752                 next = rb_entry_rq(rbnext);
753         else {
754                 rbnext = rb_first(&cfqq->sort_list);
755                 if (rbnext && rbnext != &last->rb_node)
756                         next = rb_entry_rq(rbnext);
757         }
758
759         return cfq_choose_req(cfqd, next, prev, blk_rq_pos(last));
760 }
761
762 static unsigned long cfq_slice_offset(struct cfq_data *cfqd,
763                                       struct cfq_queue *cfqq)
764 {
765         /*
766          * just an approximation, should be ok.
767          */
768         return (cfqq->cfqg->nr_cfqq - 1) * (cfq_prio_slice(cfqd, 1, 0) -
769                        cfq_prio_slice(cfqd, cfq_cfqq_sync(cfqq), cfqq->ioprio));
770 }
771
772 static inline s64
773 cfqg_key(struct cfq_rb_root *st, struct cfq_group *cfqg)
774 {
775         return cfqg->vdisktime - st->min_vdisktime;
776 }
777
778 static void
779 __cfq_group_service_tree_add(struct cfq_rb_root *st, struct cfq_group *cfqg)
780 {
781         struct rb_node **node = &st->rb.rb_node;
782         struct rb_node *parent = NULL;
783         struct cfq_group *__cfqg;
784         s64 key = cfqg_key(st, cfqg);
785         int left = 1;
786
787         while (*node != NULL) {
788                 parent = *node;
789                 __cfqg = rb_entry_cfqg(parent);
790
791                 if (key < cfqg_key(st, __cfqg))
792                         node = &parent->rb_left;
793                 else {
794                         node = &parent->rb_right;
795                         left = 0;
796                 }
797         }
798
799         if (left)
800                 st->left = &cfqg->rb_node;
801
802         rb_link_node(&cfqg->rb_node, parent, node);
803         rb_insert_color(&cfqg->rb_node, &st->rb);
804 }
805
806 static void
807 cfq_group_service_tree_add(struct cfq_data *cfqd, struct cfq_group *cfqg)
808 {
809         struct cfq_rb_root *st = &cfqd->grp_service_tree;
810         struct cfq_group *__cfqg;
811         struct rb_node *n;
812
813         cfqg->nr_cfqq++;
814         if (cfqg->on_st)
815                 return;
816
817         /*
818          * Currently put the group at the end. Later implement something
819          * so that groups get lesser vtime based on their weights, so that
820          * if group does not loose all if it was not continously backlogged.
821          */
822         n = rb_last(&st->rb);
823         if (n) {
824                 __cfqg = rb_entry_cfqg(n);
825                 cfqg->vdisktime = __cfqg->vdisktime + CFQ_IDLE_DELAY;
826         } else
827                 cfqg->vdisktime = st->min_vdisktime;
828
829         __cfq_group_service_tree_add(st, cfqg);
830         cfqg->on_st = true;
831         cfqd->nr_groups++;
832         st->total_weight += cfqg->weight;
833 }
834
835 static void
836 cfq_group_service_tree_del(struct cfq_data *cfqd, struct cfq_group *cfqg)
837 {
838         struct cfq_rb_root *st = &cfqd->grp_service_tree;
839
840         if (st->active == &cfqg->rb_node)
841                 st->active = NULL;
842
843         BUG_ON(cfqg->nr_cfqq < 1);
844         cfqg->nr_cfqq--;
845
846         /* If there are other cfq queues under this group, don't delete it */
847         if (cfqg->nr_cfqq)
848                 return;
849
850         cfq_log_cfqg(cfqd, cfqg, "del_from_rr group");
851         cfqg->on_st = false;
852         cfqd->nr_groups--;
853         st->total_weight -= cfqg->weight;
854         if (!RB_EMPTY_NODE(&cfqg->rb_node))
855                 cfq_rb_erase(&cfqg->rb_node, st);
856         cfqg->saved_workload_slice = 0;
857         blkiocg_update_blkio_group_dequeue_stats(&cfqg->blkg, 1);
858 }
859
860 static inline unsigned int cfq_cfqq_slice_usage(struct cfq_queue *cfqq)
861 {
862         unsigned int slice_used, allocated_slice;
863
864         /*
865          * Queue got expired before even a single request completed or
866          * got expired immediately after first request completion.
867          */
868         if (!cfqq->slice_start || cfqq->slice_start == jiffies) {
869                 /*
870                  * Also charge the seek time incurred to the group, otherwise
871                  * if there are mutiple queues in the group, each can dispatch
872                  * a single request on seeky media and cause lots of seek time
873                  * and group will never know it.
874                  */
875                 slice_used = max_t(unsigned, (jiffies - cfqq->dispatch_start),
876                                         1);
877         } else {
878                 slice_used = jiffies - cfqq->slice_start;
879                 allocated_slice = cfqq->slice_end - cfqq->slice_start;
880                 if (slice_used > allocated_slice)
881                         slice_used = allocated_slice;
882         }
883
884         cfq_log_cfqq(cfqq->cfqd, cfqq, "sl_used=%u sect=%lu", slice_used,
885                                 cfqq->nr_sectors);
886         return slice_used;
887 }
888
889 static void cfq_group_served(struct cfq_data *cfqd, struct cfq_group *cfqg,
890                                 struct cfq_queue *cfqq)
891 {
892         struct cfq_rb_root *st = &cfqd->grp_service_tree;
893         unsigned int used_sl;
894
895         used_sl = cfq_cfqq_slice_usage(cfqq);
896
897         /* Can't update vdisktime while group is on service tree */
898         cfq_rb_erase(&cfqg->rb_node, st);
899         cfqg->vdisktime += cfq_scale_slice(used_sl, cfqg);
900         __cfq_group_service_tree_add(st, cfqg);
901
902         /* This group is being expired. Save the context */
903         if (time_after(cfqd->workload_expires, jiffies)) {
904                 cfqg->saved_workload_slice = cfqd->workload_expires
905                                                 - jiffies;
906                 cfqg->saved_workload = cfqd->serving_type;
907                 cfqg->saved_serving_prio = cfqd->serving_prio;
908         } else
909                 cfqg->saved_workload_slice = 0;
910
911         cfq_log_cfqg(cfqd, cfqg, "served: vt=%llu min_vt=%llu", cfqg->vdisktime,
912                                         st->min_vdisktime);
913         blkiocg_update_blkio_group_stats(&cfqg->blkg, used_sl,
914                                                 cfqq->nr_sectors);
915 }
916
917 #ifdef CONFIG_CFQ_GROUP_IOSCHED
918 static inline struct cfq_group *cfqg_of_blkg(struct blkio_group *blkg)
919 {
920         if (blkg)
921                 return container_of(blkg, struct cfq_group, blkg);
922         return NULL;
923 }
924
925 static struct cfq_group *
926 cfq_find_alloc_cfqg(struct cfq_data *cfqd, struct cgroup *cgroup, int create)
927 {
928         struct blkio_cgroup *blkcg = cgroup_to_blkio_cgroup(cgroup);
929         struct cfq_group *cfqg = NULL;
930         void *key = cfqd;
931         int i, j;
932         struct cfq_rb_root *st;
933         struct backing_dev_info *bdi = &cfqd->queue->backing_dev_info;
934         unsigned int major, minor;
935
936         /* Do we need to take this reference */
937         if (!css_tryget(&blkcg->css))
938                 return NULL;;
939
940         cfqg = cfqg_of_blkg(blkiocg_lookup_group(blkcg, key));
941         if (cfqg || !create)
942                 goto done;
943
944         cfqg = kzalloc_node(sizeof(*cfqg), GFP_ATOMIC, cfqd->queue->node);
945         if (!cfqg)
946                 goto done;
947
948         cfqg->weight = blkcg->weight;
949         for_each_cfqg_st(cfqg, i, j, st)
950                 *st = CFQ_RB_ROOT;
951         RB_CLEAR_NODE(&cfqg->rb_node);
952
953         /*
954          * Take the initial reference that will be released on destroy
955          * This can be thought of a joint reference by cgroup and
956          * elevator which will be dropped by either elevator exit
957          * or cgroup deletion path depending on who is exiting first.
958          */
959         atomic_set(&cfqg->ref, 1);
960
961         /* Add group onto cgroup list */
962         sscanf(dev_name(bdi->dev), "%u:%u", &major, &minor);
963         blkiocg_add_blkio_group(blkcg, &cfqg->blkg, (void *)cfqd,
964                                         MKDEV(major, minor));
965
966         /* Add group on cfqd list */
967         hlist_add_head(&cfqg->cfqd_node, &cfqd->cfqg_list);
968
969 done:
970         css_put(&blkcg->css);
971         return cfqg;
972 }
973
974 /*
975  * Search for the cfq group current task belongs to. If create = 1, then also
976  * create the cfq group if it does not exist. request_queue lock must be held.
977  */
978 static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd, int create)
979 {
980         struct cgroup *cgroup;
981         struct cfq_group *cfqg = NULL;
982
983         rcu_read_lock();
984         cgroup = task_cgroup(current, blkio_subsys_id);
985         cfqg = cfq_find_alloc_cfqg(cfqd, cgroup, create);
986         if (!cfqg && create)
987                 cfqg = &cfqd->root_group;
988         rcu_read_unlock();
989         return cfqg;
990 }
991
992 static void cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg)
993 {
994         /* Currently, all async queues are mapped to root group */
995         if (!cfq_cfqq_sync(cfqq))
996                 cfqg = &cfqq->cfqd->root_group;
997
998         cfqq->cfqg = cfqg;
999         /* cfqq reference on cfqg */
1000         atomic_inc(&cfqq->cfqg->ref);
1001 }
1002
1003 static void cfq_put_cfqg(struct cfq_group *cfqg)
1004 {
1005         struct cfq_rb_root *st;
1006         int i, j;
1007
1008         BUG_ON(atomic_read(&cfqg->ref) <= 0);
1009         if (!atomic_dec_and_test(&cfqg->ref))
1010                 return;
1011         for_each_cfqg_st(cfqg, i, j, st)
1012                 BUG_ON(!RB_EMPTY_ROOT(&st->rb) || st->active != NULL);
1013         kfree(cfqg);
1014 }
1015
1016 static void cfq_destroy_cfqg(struct cfq_data *cfqd, struct cfq_group *cfqg)
1017 {
1018         /* Something wrong if we are trying to remove same group twice */
1019         BUG_ON(hlist_unhashed(&cfqg->cfqd_node));
1020
1021         hlist_del_init(&cfqg->cfqd_node);
1022
1023         /*
1024          * Put the reference taken at the time of creation so that when all
1025          * queues are gone, group can be destroyed.
1026          */
1027         cfq_put_cfqg(cfqg);
1028 }
1029
1030 static void cfq_release_cfq_groups(struct cfq_data *cfqd)
1031 {
1032         struct hlist_node *pos, *n;
1033         struct cfq_group *cfqg;
1034
1035         hlist_for_each_entry_safe(cfqg, pos, n, &cfqd->cfqg_list, cfqd_node) {
1036                 /*
1037                  * If cgroup removal path got to blk_group first and removed
1038                  * it from cgroup list, then it will take care of destroying
1039                  * cfqg also.
1040                  */
1041                 if (!blkiocg_del_blkio_group(&cfqg->blkg))
1042                         cfq_destroy_cfqg(cfqd, cfqg);
1043         }
1044 }
1045
1046 /*
1047  * Blk cgroup controller notification saying that blkio_group object is being
1048  * delinked as associated cgroup object is going away. That also means that
1049  * no new IO will come in this group. So get rid of this group as soon as
1050  * any pending IO in the group is finished.
1051  *
1052  * This function is called under rcu_read_lock(). key is the rcu protected
1053  * pointer. That means "key" is a valid cfq_data pointer as long as we are rcu
1054  * read lock.
1055  *
1056  * "key" was fetched from blkio_group under blkio_cgroup->lock. That means
1057  * it should not be NULL as even if elevator was exiting, cgroup deltion
1058  * path got to it first.
1059  */
1060 void cfq_unlink_blkio_group(void *key, struct blkio_group *blkg)
1061 {
1062         unsigned long  flags;
1063         struct cfq_data *cfqd = key;
1064
1065         spin_lock_irqsave(cfqd->queue->queue_lock, flags);
1066         cfq_destroy_cfqg(cfqd, cfqg_of_blkg(blkg));
1067         spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
1068 }
1069
1070 #else /* GROUP_IOSCHED */
1071 static struct cfq_group *cfq_get_cfqg(struct cfq_data *cfqd, int create)
1072 {
1073         return &cfqd->root_group;
1074 }
1075 static inline void
1076 cfq_link_cfqq_cfqg(struct cfq_queue *cfqq, struct cfq_group *cfqg) {
1077         cfqq->cfqg = cfqg;
1078 }
1079
1080 static void cfq_release_cfq_groups(struct cfq_data *cfqd) {}
1081 static inline void cfq_put_cfqg(struct cfq_group *cfqg) {}
1082
1083 #endif /* GROUP_IOSCHED */
1084
1085 /*
1086  * The cfqd->service_trees holds all pending cfq_queue's that have
1087  * requests waiting to be processed. It is sorted in the order that
1088  * we will service the queues.
1089  */
1090 static void cfq_service_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1091                                  bool add_front)
1092 {
1093         struct rb_node **p, *parent;
1094         struct cfq_queue *__cfqq;
1095         unsigned long rb_key;
1096         struct cfq_rb_root *service_tree;
1097         int left;
1098         int new_cfqq = 1;
1099
1100         service_tree = service_tree_for(cfqq->cfqg, cfqq_prio(cfqq),
1101                                                 cfqq_type(cfqq), cfqd);
1102         if (cfq_class_idle(cfqq)) {
1103                 rb_key = CFQ_IDLE_DELAY;
1104                 parent = rb_last(&service_tree->rb);
1105                 if (parent && parent != &cfqq->rb_node) {
1106                         __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
1107                         rb_key += __cfqq->rb_key;
1108                 } else
1109                         rb_key += jiffies;
1110         } else if (!add_front) {
1111                 /*
1112                  * Get our rb key offset. Subtract any residual slice
1113                  * value carried from last service. A negative resid
1114                  * count indicates slice overrun, and this should position
1115                  * the next service time further away in the tree.
1116                  */
1117                 rb_key = cfq_slice_offset(cfqd, cfqq) + jiffies;
1118                 rb_key -= cfqq->slice_resid;
1119                 cfqq->slice_resid = 0;
1120         } else {
1121                 rb_key = -HZ;
1122                 __cfqq = cfq_rb_first(service_tree);
1123                 rb_key += __cfqq ? __cfqq->rb_key : jiffies;
1124         }
1125
1126         if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
1127                 new_cfqq = 0;
1128                 /*
1129                  * same position, nothing more to do
1130                  */
1131                 if (rb_key == cfqq->rb_key &&
1132                     cfqq->service_tree == service_tree)
1133                         return;
1134
1135                 cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
1136                 cfqq->service_tree = NULL;
1137         }
1138
1139         left = 1;
1140         parent = NULL;
1141         cfqq->service_tree = service_tree;
1142         p = &service_tree->rb.rb_node;
1143         while (*p) {
1144                 struct rb_node **n;
1145
1146                 parent = *p;
1147                 __cfqq = rb_entry(parent, struct cfq_queue, rb_node);
1148
1149                 /*
1150                  * sort by key, that represents service time.
1151                  */
1152                 if (time_before(rb_key, __cfqq->rb_key))
1153                         n = &(*p)->rb_left;
1154                 else {
1155                         n = &(*p)->rb_right;
1156                         left = 0;
1157                 }
1158
1159                 p = n;
1160         }
1161
1162         if (left)
1163                 service_tree->left = &cfqq->rb_node;
1164
1165         cfqq->rb_key = rb_key;
1166         rb_link_node(&cfqq->rb_node, parent, p);
1167         rb_insert_color(&cfqq->rb_node, &service_tree->rb);
1168         service_tree->count++;
1169         if (add_front || !new_cfqq)
1170                 return;
1171         cfq_group_service_tree_add(cfqd, cfqq->cfqg);
1172 }
1173
1174 static struct cfq_queue *
1175 cfq_prio_tree_lookup(struct cfq_data *cfqd, struct rb_root *root,
1176                      sector_t sector, struct rb_node **ret_parent,
1177                      struct rb_node ***rb_link)
1178 {
1179         struct rb_node **p, *parent;
1180         struct cfq_queue *cfqq = NULL;
1181
1182         parent = NULL;
1183         p = &root->rb_node;
1184         while (*p) {
1185                 struct rb_node **n;
1186
1187                 parent = *p;
1188                 cfqq = rb_entry(parent, struct cfq_queue, p_node);
1189
1190                 /*
1191                  * Sort strictly based on sector.  Smallest to the left,
1192                  * largest to the right.
1193                  */
1194                 if (sector > blk_rq_pos(cfqq->next_rq))
1195                         n = &(*p)->rb_right;
1196                 else if (sector < blk_rq_pos(cfqq->next_rq))
1197                         n = &(*p)->rb_left;
1198                 else
1199                         break;
1200                 p = n;
1201                 cfqq = NULL;
1202         }
1203
1204         *ret_parent = parent;
1205         if (rb_link)
1206                 *rb_link = p;
1207         return cfqq;
1208 }
1209
1210 static void cfq_prio_tree_add(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1211 {
1212         struct rb_node **p, *parent;
1213         struct cfq_queue *__cfqq;
1214
1215         if (cfqq->p_root) {
1216                 rb_erase(&cfqq->p_node, cfqq->p_root);
1217                 cfqq->p_root = NULL;
1218         }
1219
1220         if (cfq_class_idle(cfqq))
1221                 return;
1222         if (!cfqq->next_rq)
1223                 return;
1224
1225         cfqq->p_root = &cfqd->prio_trees[cfqq->org_ioprio];
1226         __cfqq = cfq_prio_tree_lookup(cfqd, cfqq->p_root,
1227                                       blk_rq_pos(cfqq->next_rq), &parent, &p);
1228         if (!__cfqq) {
1229                 rb_link_node(&cfqq->p_node, parent, p);
1230                 rb_insert_color(&cfqq->p_node, cfqq->p_root);
1231         } else
1232                 cfqq->p_root = NULL;
1233 }
1234
1235 /*
1236  * Update cfqq's position in the service tree.
1237  */
1238 static void cfq_resort_rr_list(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1239 {
1240         /*
1241          * Resorting requires the cfqq to be on the RR list already.
1242          */
1243         if (cfq_cfqq_on_rr(cfqq)) {
1244                 cfq_service_tree_add(cfqd, cfqq, 0);
1245                 cfq_prio_tree_add(cfqd, cfqq);
1246         }
1247 }
1248
1249 /*
1250  * add to busy list of queues for service, trying to be fair in ordering
1251  * the pending list according to last request service
1252  */
1253 static void cfq_add_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1254 {
1255         cfq_log_cfqq(cfqd, cfqq, "add_to_rr");
1256         BUG_ON(cfq_cfqq_on_rr(cfqq));
1257         cfq_mark_cfqq_on_rr(cfqq);
1258         cfqd->busy_queues++;
1259
1260         cfq_resort_rr_list(cfqd, cfqq);
1261 }
1262
1263 /*
1264  * Called when the cfqq no longer has requests pending, remove it from
1265  * the service tree.
1266  */
1267 static void cfq_del_cfqq_rr(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1268 {
1269         cfq_log_cfqq(cfqd, cfqq, "del_from_rr");
1270         BUG_ON(!cfq_cfqq_on_rr(cfqq));
1271         cfq_clear_cfqq_on_rr(cfqq);
1272
1273         if (!RB_EMPTY_NODE(&cfqq->rb_node)) {
1274                 cfq_rb_erase(&cfqq->rb_node, cfqq->service_tree);
1275                 cfqq->service_tree = NULL;
1276         }
1277         if (cfqq->p_root) {
1278                 rb_erase(&cfqq->p_node, cfqq->p_root);
1279                 cfqq->p_root = NULL;
1280         }
1281
1282         cfq_group_service_tree_del(cfqd, cfqq->cfqg);
1283         BUG_ON(!cfqd->busy_queues);
1284         cfqd->busy_queues--;
1285 }
1286
1287 /*
1288  * rb tree support functions
1289  */
1290 static void cfq_del_rq_rb(struct request *rq)
1291 {
1292         struct cfq_queue *cfqq = RQ_CFQQ(rq);
1293         const int sync = rq_is_sync(rq);
1294
1295         BUG_ON(!cfqq->queued[sync]);
1296         cfqq->queued[sync]--;
1297
1298         elv_rb_del(&cfqq->sort_list, rq);
1299
1300         if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list)) {
1301                 /*
1302                  * Queue will be deleted from service tree when we actually
1303                  * expire it later. Right now just remove it from prio tree
1304                  * as it is empty.
1305                  */
1306                 if (cfqq->p_root) {
1307                         rb_erase(&cfqq->p_node, cfqq->p_root);
1308                         cfqq->p_root = NULL;
1309                 }
1310         }
1311 }
1312
1313 static void cfq_add_rq_rb(struct request *rq)
1314 {
1315         struct cfq_queue *cfqq = RQ_CFQQ(rq);
1316         struct cfq_data *cfqd = cfqq->cfqd;
1317         struct request *__alias, *prev;
1318
1319         cfqq->queued[rq_is_sync(rq)]++;
1320
1321         /*
1322          * looks a little odd, but the first insert might return an alias.
1323          * if that happens, put the alias on the dispatch list
1324          */
1325         while ((__alias = elv_rb_add(&cfqq->sort_list, rq)) != NULL)
1326                 cfq_dispatch_insert(cfqd->queue, __alias);
1327
1328         if (!cfq_cfqq_on_rr(cfqq))
1329                 cfq_add_cfqq_rr(cfqd, cfqq);
1330
1331         /*
1332          * check if this request is a better next-serve candidate
1333          */
1334         prev = cfqq->next_rq;
1335         cfqq->next_rq = cfq_choose_req(cfqd, cfqq->next_rq, rq, cfqd->last_position);
1336
1337         /*
1338          * adjust priority tree position, if ->next_rq changes
1339          */
1340         if (prev != cfqq->next_rq)
1341                 cfq_prio_tree_add(cfqd, cfqq);
1342
1343         BUG_ON(!cfqq->next_rq);
1344 }
1345
1346 static void cfq_reposition_rq_rb(struct cfq_queue *cfqq, struct request *rq)
1347 {
1348         elv_rb_del(&cfqq->sort_list, rq);
1349         cfqq->queued[rq_is_sync(rq)]--;
1350         cfq_add_rq_rb(rq);
1351 }
1352
1353 static struct request *
1354 cfq_find_rq_fmerge(struct cfq_data *cfqd, struct bio *bio)
1355 {
1356         struct task_struct *tsk = current;
1357         struct cfq_io_context *cic;
1358         struct cfq_queue *cfqq;
1359
1360         cic = cfq_cic_lookup(cfqd, tsk->io_context);
1361         if (!cic)
1362                 return NULL;
1363
1364         cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
1365         if (cfqq) {
1366                 sector_t sector = bio->bi_sector + bio_sectors(bio);
1367
1368                 return elv_rb_find(&cfqq->sort_list, sector);
1369         }
1370
1371         return NULL;
1372 }
1373
1374 static void cfq_activate_request(struct request_queue *q, struct request *rq)
1375 {
1376         struct cfq_data *cfqd = q->elevator->elevator_data;
1377
1378         cfqd->rq_in_driver[rq_is_sync(rq)]++;
1379         cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "activate rq, drv=%d",
1380                                                 rq_in_driver(cfqd));
1381
1382         cfqd->last_position = blk_rq_pos(rq) + blk_rq_sectors(rq);
1383 }
1384
1385 static void cfq_deactivate_request(struct request_queue *q, struct request *rq)
1386 {
1387         struct cfq_data *cfqd = q->elevator->elevator_data;
1388         const int sync = rq_is_sync(rq);
1389
1390         WARN_ON(!cfqd->rq_in_driver[sync]);
1391         cfqd->rq_in_driver[sync]--;
1392         cfq_log_cfqq(cfqd, RQ_CFQQ(rq), "deactivate rq, drv=%d",
1393                                                 rq_in_driver(cfqd));
1394 }
1395
1396 static void cfq_remove_request(struct request *rq)
1397 {
1398         struct cfq_queue *cfqq = RQ_CFQQ(rq);
1399
1400         if (cfqq->next_rq == rq)
1401                 cfqq->next_rq = cfq_find_next_rq(cfqq->cfqd, cfqq, rq);
1402
1403         list_del_init(&rq->queuelist);
1404         cfq_del_rq_rb(rq);
1405
1406         cfqq->cfqd->rq_queued--;
1407         if (rq_is_meta(rq)) {
1408                 WARN_ON(!cfqq->meta_pending);
1409                 cfqq->meta_pending--;
1410         }
1411 }
1412
1413 static int cfq_merge(struct request_queue *q, struct request **req,
1414                      struct bio *bio)
1415 {
1416         struct cfq_data *cfqd = q->elevator->elevator_data;
1417         struct request *__rq;
1418
1419         __rq = cfq_find_rq_fmerge(cfqd, bio);
1420         if (__rq && elv_rq_merge_ok(__rq, bio)) {
1421                 *req = __rq;
1422                 return ELEVATOR_FRONT_MERGE;
1423         }
1424
1425         return ELEVATOR_NO_MERGE;
1426 }
1427
1428 static void cfq_merged_request(struct request_queue *q, struct request *req,
1429                                int type)
1430 {
1431         if (type == ELEVATOR_FRONT_MERGE) {
1432                 struct cfq_queue *cfqq = RQ_CFQQ(req);
1433
1434                 cfq_reposition_rq_rb(cfqq, req);
1435         }
1436 }
1437
1438 static void
1439 cfq_merged_requests(struct request_queue *q, struct request *rq,
1440                     struct request *next)
1441 {
1442         struct cfq_queue *cfqq = RQ_CFQQ(rq);
1443         /*
1444          * reposition in fifo if next is older than rq
1445          */
1446         if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
1447             time_before(rq_fifo_time(next), rq_fifo_time(rq))) {
1448                 list_move(&rq->queuelist, &next->queuelist);
1449                 rq_set_fifo_time(rq, rq_fifo_time(next));
1450         }
1451
1452         if (cfqq->next_rq == next)
1453                 cfqq->next_rq = rq;
1454         cfq_remove_request(next);
1455 }
1456
1457 static int cfq_allow_merge(struct request_queue *q, struct request *rq,
1458                            struct bio *bio)
1459 {
1460         struct cfq_data *cfqd = q->elevator->elevator_data;
1461         struct cfq_io_context *cic;
1462         struct cfq_queue *cfqq;
1463
1464         /* Deny merge if bio and rq don't belong to same cfq group */
1465         if ((RQ_CFQQ(rq))->cfqg != cfq_get_cfqg(cfqd, 0))
1466                 return false;
1467         /*
1468          * Disallow merge of a sync bio into an async request.
1469          */
1470         if (cfq_bio_sync(bio) && !rq_is_sync(rq))
1471                 return false;
1472
1473         /*
1474          * Lookup the cfqq that this bio will be queued with. Allow
1475          * merge only if rq is queued there.
1476          */
1477         cic = cfq_cic_lookup(cfqd, current->io_context);
1478         if (!cic)
1479                 return false;
1480
1481         cfqq = cic_to_cfqq(cic, cfq_bio_sync(bio));
1482         return cfqq == RQ_CFQQ(rq);
1483 }
1484
1485 static void __cfq_set_active_queue(struct cfq_data *cfqd,
1486                                    struct cfq_queue *cfqq)
1487 {
1488         if (cfqq) {
1489                 cfq_log_cfqq(cfqd, cfqq, "set_active");
1490                 cfqq->slice_start = 0;
1491                 cfqq->dispatch_start = jiffies;
1492                 cfqq->slice_end = 0;
1493                 cfqq->slice_dispatch = 0;
1494                 cfqq->nr_sectors = 0;
1495
1496                 cfq_clear_cfqq_wait_request(cfqq);
1497                 cfq_clear_cfqq_must_dispatch(cfqq);
1498                 cfq_clear_cfqq_must_alloc_slice(cfqq);
1499                 cfq_clear_cfqq_fifo_expire(cfqq);
1500                 cfq_mark_cfqq_slice_new(cfqq);
1501
1502                 del_timer(&cfqd->idle_slice_timer);
1503         }
1504
1505         cfqd->active_queue = cfqq;
1506 }
1507
1508 /*
1509  * current cfqq expired its slice (or was too idle), select new one
1510  */
1511 static void
1512 __cfq_slice_expired(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1513                     bool timed_out)
1514 {
1515         cfq_log_cfqq(cfqd, cfqq, "slice expired t=%d", timed_out);
1516
1517         if (cfq_cfqq_wait_request(cfqq))
1518                 del_timer(&cfqd->idle_slice_timer);
1519
1520         cfq_clear_cfqq_wait_request(cfqq);
1521
1522         /*
1523          * store what was left of this slice, if the queue idled/timed out
1524          */
1525         if (timed_out && !cfq_cfqq_slice_new(cfqq)) {
1526                 cfqq->slice_resid = cfqq->slice_end - jiffies;
1527                 cfq_log_cfqq(cfqd, cfqq, "resid=%ld", cfqq->slice_resid);
1528         }
1529
1530         cfq_group_served(cfqd, cfqq->cfqg, cfqq);
1531
1532         if (cfq_cfqq_on_rr(cfqq) && RB_EMPTY_ROOT(&cfqq->sort_list))
1533                 cfq_del_cfqq_rr(cfqd, cfqq);
1534
1535         cfq_resort_rr_list(cfqd, cfqq);
1536
1537         if (cfqq == cfqd->active_queue)
1538                 cfqd->active_queue = NULL;
1539
1540         if (&cfqq->cfqg->rb_node == cfqd->grp_service_tree.active)
1541                 cfqd->grp_service_tree.active = NULL;
1542
1543         if (cfqd->active_cic) {
1544                 put_io_context(cfqd->active_cic->ioc);
1545                 cfqd->active_cic = NULL;
1546         }
1547 }
1548
1549 static inline void cfq_slice_expired(struct cfq_data *cfqd, bool timed_out)
1550 {
1551         struct cfq_queue *cfqq = cfqd->active_queue;
1552
1553         if (cfqq)
1554                 __cfq_slice_expired(cfqd, cfqq, timed_out);
1555 }
1556
1557 /*
1558  * Get next queue for service. Unless we have a queue preemption,
1559  * we'll simply select the first cfqq in the service tree.
1560  */
1561 static struct cfq_queue *cfq_get_next_queue(struct cfq_data *cfqd)
1562 {
1563         struct cfq_rb_root *service_tree =
1564                 service_tree_for(cfqd->serving_group, cfqd->serving_prio,
1565                                         cfqd->serving_type, cfqd);
1566
1567         if (!cfqd->rq_queued)
1568                 return NULL;
1569
1570         /* There is nothing to dispatch */
1571         if (!service_tree)
1572                 return NULL;
1573         if (RB_EMPTY_ROOT(&service_tree->rb))
1574                 return NULL;
1575         return cfq_rb_first(service_tree);
1576 }
1577
1578 static struct cfq_queue *cfq_get_next_queue_forced(struct cfq_data *cfqd)
1579 {
1580         struct cfq_group *cfqg;
1581         struct cfq_queue *cfqq;
1582         int i, j;
1583         struct cfq_rb_root *st;
1584
1585         if (!cfqd->rq_queued)
1586                 return NULL;
1587
1588         cfqg = cfq_get_next_cfqg(cfqd);
1589         if (!cfqg)
1590                 return NULL;
1591
1592         for_each_cfqg_st(cfqg, i, j, st)
1593                 if ((cfqq = cfq_rb_first(st)) != NULL)
1594                         return cfqq;
1595         return NULL;
1596 }
1597
1598 /*
1599  * Get and set a new active queue for service.
1600  */
1601 static struct cfq_queue *cfq_set_active_queue(struct cfq_data *cfqd,
1602                                               struct cfq_queue *cfqq)
1603 {
1604         if (!cfqq)
1605                 cfqq = cfq_get_next_queue(cfqd);
1606
1607         __cfq_set_active_queue(cfqd, cfqq);
1608         return cfqq;
1609 }
1610
1611 static inline sector_t cfq_dist_from_last(struct cfq_data *cfqd,
1612                                           struct request *rq)
1613 {
1614         if (blk_rq_pos(rq) >= cfqd->last_position)
1615                 return blk_rq_pos(rq) - cfqd->last_position;
1616         else
1617                 return cfqd->last_position - blk_rq_pos(rq);
1618 }
1619
1620 #define CFQQ_SEEK_THR           8 * 1024
1621 #define CFQQ_SEEKY(cfqq)        ((cfqq)->seek_mean > CFQQ_SEEK_THR)
1622
1623 static inline int cfq_rq_close(struct cfq_data *cfqd, struct cfq_queue *cfqq,
1624                                struct request *rq)
1625 {
1626         sector_t sdist = cfqq->seek_mean;
1627
1628         if (!sample_valid(cfqq->seek_samples))
1629                 sdist = CFQQ_SEEK_THR;
1630
1631         return cfq_dist_from_last(cfqd, rq) <= sdist;
1632 }
1633
1634 static struct cfq_queue *cfqq_close(struct cfq_data *cfqd,
1635                                     struct cfq_queue *cur_cfqq)
1636 {
1637         struct rb_root *root = &cfqd->prio_trees[cur_cfqq->org_ioprio];
1638         struct rb_node *parent, *node;
1639         struct cfq_queue *__cfqq;
1640         sector_t sector = cfqd->last_position;
1641
1642         if (RB_EMPTY_ROOT(root))
1643                 return NULL;
1644
1645         /*
1646          * First, if we find a request starting at the end of the last
1647          * request, choose it.
1648          */
1649         __cfqq = cfq_prio_tree_lookup(cfqd, root, sector, &parent, NULL);
1650         if (__cfqq)
1651                 return __cfqq;
1652
1653         /*
1654          * If the exact sector wasn't found, the parent of the NULL leaf
1655          * will contain the closest sector.
1656          */
1657         __cfqq = rb_entry(parent, struct cfq_queue, p_node);
1658         if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
1659                 return __cfqq;
1660
1661         if (blk_rq_pos(__cfqq->next_rq) < sector)
1662                 node = rb_next(&__cfqq->p_node);
1663         else
1664                 node = rb_prev(&__cfqq->p_node);
1665         if (!node)
1666                 return NULL;
1667
1668         __cfqq = rb_entry(node, struct cfq_queue, p_node);
1669         if (cfq_rq_close(cfqd, cur_cfqq, __cfqq->next_rq))
1670                 return __cfqq;
1671
1672         return NULL;
1673 }
1674
1675 /*
1676  * cfqd - obvious
1677  * cur_cfqq - passed in so that we don't decide that the current queue is
1678  *            closely cooperating with itself.
1679  *
1680  * So, basically we're assuming that that cur_cfqq has dispatched at least
1681  * one request, and that cfqd->last_position reflects a position on the disk
1682  * associated with the I/O issued by cur_cfqq.  I'm not sure this is a valid
1683  * assumption.
1684  */
1685 static struct cfq_queue *cfq_close_cooperator(struct cfq_data *cfqd,
1686                                               struct cfq_queue *cur_cfqq)
1687 {
1688         struct cfq_queue *cfqq;
1689
1690         if (!cfq_cfqq_sync(cur_cfqq))
1691                 return NULL;
1692         if (CFQQ_SEEKY(cur_cfqq))
1693                 return NULL;
1694
1695         /*
1696          * We should notice if some of the queues are cooperating, eg
1697          * working closely on the same area of the disk. In that case,
1698          * we can group them together and don't waste time idling.
1699          */
1700         cfqq = cfqq_close(cfqd, cur_cfqq);
1701         if (!cfqq)
1702                 return NULL;
1703
1704         /* If new queue belongs to different cfq_group, don't choose it */
1705         if (cur_cfqq->cfqg != cfqq->cfqg)
1706                 return NULL;
1707
1708         /*
1709          * It only makes sense to merge sync queues.
1710          */
1711         if (!cfq_cfqq_sync(cfqq))
1712                 return NULL;
1713         if (CFQQ_SEEKY(cfqq))
1714                 return NULL;
1715
1716         /*
1717          * Do not merge queues of different priority classes
1718          */
1719         if (cfq_class_rt(cfqq) != cfq_class_rt(cur_cfqq))
1720                 return NULL;
1721
1722         return cfqq;
1723 }
1724
1725 /*
1726  * Determine whether we should enforce idle window for this queue.
1727  */
1728
1729 static bool cfq_should_idle(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1730 {
1731         enum wl_prio_t prio = cfqq_prio(cfqq);
1732         struct cfq_rb_root *service_tree = cfqq->service_tree;
1733
1734         BUG_ON(!service_tree);
1735         BUG_ON(!service_tree->count);
1736
1737         /* We never do for idle class queues. */
1738         if (prio == IDLE_WORKLOAD)
1739                 return false;
1740
1741         /* We do for queues that were marked with idle window flag. */
1742         if (cfq_cfqq_idle_window(cfqq))
1743                 return true;
1744
1745         /*
1746          * Otherwise, we do only if they are the last ones
1747          * in their service tree.
1748          */
1749         return service_tree->count == 1;
1750 }
1751
1752 static void cfq_arm_slice_timer(struct cfq_data *cfqd)
1753 {
1754         struct cfq_queue *cfqq = cfqd->active_queue;
1755         struct cfq_io_context *cic;
1756         unsigned long sl;
1757
1758         /*
1759          * SSD device without seek penalty, disable idling. But only do so
1760          * for devices that support queuing, otherwise we still have a problem
1761          * with sync vs async workloads.
1762          */
1763         if (blk_queue_nonrot(cfqd->queue) && cfqd->hw_tag)
1764                 return;
1765
1766         WARN_ON(!RB_EMPTY_ROOT(&cfqq->sort_list));
1767         WARN_ON(cfq_cfqq_slice_new(cfqq));
1768
1769         /*
1770          * idle is disabled, either manually or by past process history
1771          */
1772         if (!cfqd->cfq_slice_idle || !cfq_should_idle(cfqd, cfqq))
1773                 return;
1774
1775         /*
1776          * still active requests from this queue, don't idle
1777          */
1778         if (cfqq->dispatched)
1779                 return;
1780
1781         /*
1782          * task has exited, don't wait
1783          */
1784         cic = cfqd->active_cic;
1785         if (!cic || !atomic_read(&cic->ioc->nr_tasks))
1786                 return;
1787
1788         /*
1789          * If our average think time is larger than the remaining time
1790          * slice, then don't idle. This avoids overrunning the allotted
1791          * time slice.
1792          */
1793         if (sample_valid(cic->ttime_samples) &&
1794             (cfqq->slice_end - jiffies < cic->ttime_mean))
1795                 return;
1796
1797         cfq_mark_cfqq_wait_request(cfqq);
1798
1799         sl = cfqd->cfq_slice_idle;
1800
1801         mod_timer(&cfqd->idle_slice_timer, jiffies + sl);
1802         cfq_log_cfqq(cfqd, cfqq, "arm_idle: %lu", sl);
1803 }
1804
1805 /*
1806  * Move request from internal lists to the request queue dispatch list.
1807  */
1808 static void cfq_dispatch_insert(struct request_queue *q, struct request *rq)
1809 {
1810         struct cfq_data *cfqd = q->elevator->elevator_data;
1811         struct cfq_queue *cfqq = RQ_CFQQ(rq);
1812
1813         cfq_log_cfqq(cfqd, cfqq, "dispatch_insert");
1814
1815         cfqq->next_rq = cfq_find_next_rq(cfqd, cfqq, rq);
1816         cfq_remove_request(rq);
1817         cfqq->dispatched++;
1818         elv_dispatch_sort(q, rq);
1819
1820         if (cfq_cfqq_sync(cfqq))
1821                 cfqd->sync_flight++;
1822         cfqq->nr_sectors += blk_rq_sectors(rq);
1823 }
1824
1825 /*
1826  * return expired entry, or NULL to just start from scratch in rbtree
1827  */
1828 static struct request *cfq_check_fifo(struct cfq_queue *cfqq)
1829 {
1830         struct request *rq = NULL;
1831
1832         if (cfq_cfqq_fifo_expire(cfqq))
1833                 return NULL;
1834
1835         cfq_mark_cfqq_fifo_expire(cfqq);
1836
1837         if (list_empty(&cfqq->fifo))
1838                 return NULL;
1839
1840         rq = rq_entry_fifo(cfqq->fifo.next);
1841         if (time_before(jiffies, rq_fifo_time(rq)))
1842                 rq = NULL;
1843
1844         cfq_log_cfqq(cfqq->cfqd, cfqq, "fifo=%p", rq);
1845         return rq;
1846 }
1847
1848 static inline int
1849 cfq_prio_to_maxrq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
1850 {
1851         const int base_rq = cfqd->cfq_slice_async_rq;
1852
1853         WARN_ON(cfqq->ioprio >= IOPRIO_BE_NR);
1854
1855         return 2 * (base_rq + base_rq * (CFQ_PRIO_LISTS - 1 - cfqq->ioprio));
1856 }
1857
1858 /*
1859  * Must be called with the queue_lock held.
1860  */
1861 static int cfqq_process_refs(struct cfq_queue *cfqq)
1862 {
1863         int process_refs, io_refs;
1864
1865         io_refs = cfqq->allocated[READ] + cfqq->allocated[WRITE];
1866         process_refs = atomic_read(&cfqq->ref) - io_refs;
1867         BUG_ON(process_refs < 0);
1868         return process_refs;
1869 }
1870
1871 static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
1872 {
1873         int process_refs, new_process_refs;
1874         struct cfq_queue *__cfqq;
1875
1876         /* Avoid a circular list and skip interim queue merges */
1877         while ((__cfqq = new_cfqq->new_cfqq)) {
1878                 if (__cfqq == cfqq)
1879                         return;
1880                 new_cfqq = __cfqq;
1881         }
1882
1883         process_refs = cfqq_process_refs(cfqq);
1884         /*
1885          * If the process for the cfqq has gone away, there is no
1886          * sense in merging the queues.
1887          */
1888         if (process_refs == 0)
1889                 return;
1890
1891         /*
1892          * Merge in the direction of the lesser amount of work.
1893          */
1894         new_process_refs = cfqq_process_refs(new_cfqq);
1895         if (new_process_refs >= process_refs) {
1896                 cfqq->new_cfqq = new_cfqq;
1897                 atomic_add(process_refs, &new_cfqq->ref);
1898         } else {
1899                 new_cfqq->new_cfqq = cfqq;
1900                 atomic_add(new_process_refs, &cfqq->ref);
1901         }
1902 }
1903
1904 static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd,
1905                                 struct cfq_group *cfqg, enum wl_prio_t prio,
1906                                 bool prio_changed)
1907 {
1908         struct cfq_queue *queue;
1909         int i;
1910         bool key_valid = false;
1911         unsigned long lowest_key = 0;
1912         enum wl_type_t cur_best = SYNC_NOIDLE_WORKLOAD;
1913
1914         if (prio_changed) {
1915                 /*
1916                  * When priorities switched, we prefer starting
1917                  * from SYNC_NOIDLE (first choice), or just SYNC
1918                  * over ASYNC
1919                  */
1920                 if (service_tree_for(cfqg, prio, cur_best, cfqd)->count)
1921                         return cur_best;
1922                 cur_best = SYNC_WORKLOAD;
1923                 if (service_tree_for(cfqg, prio, cur_best, cfqd)->count)
1924                         return cur_best;
1925
1926                 return ASYNC_WORKLOAD;
1927         }
1928
1929         for (i = 0; i < 3; ++i) {
1930                 /* otherwise, select the one with lowest rb_key */
1931                 queue = cfq_rb_first(service_tree_for(cfqg, prio, i, cfqd));
1932                 if (queue &&
1933                     (!key_valid || time_before(queue->rb_key, lowest_key))) {
1934                         lowest_key = queue->rb_key;
1935                         cur_best = i;
1936                         key_valid = true;
1937                 }
1938         }
1939
1940         return cur_best;
1941 }
1942
1943 static void choose_service_tree(struct cfq_data *cfqd, struct cfq_group *cfqg)
1944 {
1945         enum wl_prio_t previous_prio = cfqd->serving_prio;
1946         bool prio_changed;
1947         unsigned slice;
1948         unsigned count;
1949         struct cfq_rb_root *st;
1950         unsigned group_slice;
1951
1952         if (!cfqg) {
1953                 cfqd->serving_prio = IDLE_WORKLOAD;
1954                 cfqd->workload_expires = jiffies + 1;
1955                 return;
1956         }
1957
1958         /* Choose next priority. RT > BE > IDLE */
1959         if (cfq_group_busy_queues_wl(RT_WORKLOAD, cfqd, cfqg))
1960                 cfqd->serving_prio = RT_WORKLOAD;
1961         else if (cfq_group_busy_queues_wl(BE_WORKLOAD, cfqd, cfqg))
1962                 cfqd->serving_prio = BE_WORKLOAD;
1963         else {
1964                 cfqd->serving_prio = IDLE_WORKLOAD;
1965                 cfqd->workload_expires = jiffies + 1;
1966                 return;
1967         }
1968
1969         /*
1970          * For RT and BE, we have to choose also the type
1971          * (SYNC, SYNC_NOIDLE, ASYNC), and to compute a workload
1972          * expiration time
1973          */
1974         prio_changed = (cfqd->serving_prio != previous_prio);
1975         st = service_tree_for(cfqg, cfqd->serving_prio, cfqd->serving_type,
1976                                 cfqd);
1977         count = st->count;
1978
1979         /*
1980          * If priority didn't change, check workload expiration,
1981          * and that we still have other queues ready
1982          */
1983         if (!prio_changed && count &&
1984             !time_after(jiffies, cfqd->workload_expires))
1985                 return;
1986
1987         /* otherwise select new workload type */
1988         cfqd->serving_type =
1989                 cfq_choose_wl(cfqd, cfqg, cfqd->serving_prio, prio_changed);
1990         st = service_tree_for(cfqg, cfqd->serving_prio, cfqd->serving_type,
1991                                 cfqd);
1992         count = st->count;
1993
1994         /*
1995          * the workload slice is computed as a fraction of target latency
1996          * proportional to the number of queues in that workload, over
1997          * all the queues in the same priority class
1998          */
1999         group_slice = cfq_group_slice(cfqd, cfqg);
2000
2001         slice = group_slice * count /
2002                 max_t(unsigned, cfqg->busy_queues_avg[cfqd->serving_prio],
2003                       cfq_group_busy_queues_wl(cfqd->serving_prio, cfqd, cfqg));
2004
2005         if (cfqd->serving_type == ASYNC_WORKLOAD)
2006                 /* async workload slice is scaled down according to
2007                  * the sync/async slice ratio. */
2008                 slice = slice * cfqd->cfq_slice[0] / cfqd->cfq_slice[1];
2009         else
2010                 /* sync workload slice is at least 2 * cfq_slice_idle */
2011                 slice = max(slice, 2 * cfqd->cfq_slice_idle);
2012
2013         slice = max_t(unsigned, slice, CFQ_MIN_TT);
2014         cfqd->workload_expires = jiffies + slice;
2015         cfqd->noidle_tree_requires_idle = false;
2016 }
2017
2018 static struct cfq_group *cfq_get_next_cfqg(struct cfq_data *cfqd)
2019 {
2020         struct cfq_rb_root *st = &cfqd->grp_service_tree;
2021         struct cfq_group *cfqg;
2022
2023         if (RB_EMPTY_ROOT(&st->rb))
2024                 return NULL;
2025         cfqg = cfq_rb_first_group(st);
2026         st->active = &cfqg->rb_node;
2027         update_min_vdisktime(st);
2028         return cfqg;
2029 }
2030
2031 static void cfq_choose_cfqg(struct cfq_data *cfqd)
2032 {
2033         struct cfq_group *cfqg = cfq_get_next_cfqg(cfqd);
2034
2035         cfqd->serving_group = cfqg;
2036
2037         /* Restore the workload type data */
2038         if (cfqg->saved_workload_slice) {
2039                 cfqd->workload_expires = jiffies + cfqg->saved_workload_slice;
2040                 cfqd->serving_type = cfqg->saved_workload;
2041                 cfqd->serving_prio = cfqg->saved_serving_prio;
2042         }
2043         choose_service_tree(cfqd, cfqg);
2044 }
2045
2046 /*
2047  * Select a queue for service. If we have a current active queue,
2048  * check whether to continue servicing it, or retrieve and set a new one.
2049  */
2050 static struct cfq_queue *cfq_select_queue(struct cfq_data *cfqd)
2051 {
2052         struct cfq_queue *cfqq, *new_cfqq = NULL;
2053
2054         cfqq = cfqd->active_queue;
2055         if (!cfqq)
2056                 goto new_queue;
2057
2058         if (!cfqd->rq_queued)
2059                 return NULL;
2060         /*
2061          * The active queue has run out of time, expire it and select new.
2062          */
2063         if (cfq_slice_used(cfqq) && !cfq_cfqq_must_dispatch(cfqq))
2064                 goto expire;
2065
2066         /*
2067          * The active queue has requests and isn't expired, allow it to
2068          * dispatch.
2069          */
2070         if (!RB_EMPTY_ROOT(&cfqq->sort_list))
2071                 goto keep_queue;
2072
2073         /*
2074          * If another queue has a request waiting within our mean seek
2075          * distance, let it run.  The expire code will check for close
2076          * cooperators and put the close queue at the front of the service
2077          * tree.  If possible, merge the expiring queue with the new cfqq.
2078          */
2079         new_cfqq = cfq_close_cooperator(cfqd, cfqq);
2080         if (new_cfqq) {
2081                 if (!cfqq->new_cfqq)
2082                         cfq_setup_merge(cfqq, new_cfqq);
2083                 goto expire;
2084         }
2085
2086         /*
2087          * No requests pending. If the active queue still has requests in
2088          * flight or is idling for a new request, allow either of these
2089          * conditions to happen (or time out) before selecting a new queue.
2090          */
2091         if (timer_pending(&cfqd->idle_slice_timer) ||
2092             (cfqq->dispatched && cfq_should_idle(cfqd, cfqq))) {
2093                 cfqq = NULL;
2094                 goto keep_queue;
2095         }
2096
2097 expire:
2098         cfq_slice_expired(cfqd, 0);
2099 new_queue:
2100         /*
2101          * Current queue expired. Check if we have to switch to a new
2102          * service tree
2103          */
2104         if (!new_cfqq)
2105                 cfq_choose_cfqg(cfqd);
2106
2107         cfqq = cfq_set_active_queue(cfqd, new_cfqq);
2108 keep_queue:
2109         return cfqq;
2110 }
2111
2112 static int __cfq_forced_dispatch_cfqq(struct cfq_queue *cfqq)
2113 {
2114         int dispatched = 0;
2115
2116         while (cfqq->next_rq) {
2117                 cfq_dispatch_insert(cfqq->cfqd->queue, cfqq->next_rq);
2118                 dispatched++;
2119         }
2120
2121         BUG_ON(!list_empty(&cfqq->fifo));
2122
2123         /* By default cfqq is not expired if it is empty. Do it explicitly */
2124         __cfq_slice_expired(cfqq->cfqd, cfqq, 0);
2125         return dispatched;
2126 }
2127
2128 /*
2129  * Drain our current requests. Used for barriers and when switching
2130  * io schedulers on-the-fly.
2131  */
2132 static int cfq_forced_dispatch(struct cfq_data *cfqd)
2133 {
2134         struct cfq_queue *cfqq;
2135         int dispatched = 0;
2136
2137         while ((cfqq = cfq_get_next_queue_forced(cfqd)) != NULL)
2138                 dispatched += __cfq_forced_dispatch_cfqq(cfqq);
2139
2140         cfq_slice_expired(cfqd, 0);
2141         BUG_ON(cfqd->busy_queues);
2142
2143         cfq_log(cfqd, "forced_dispatch=%d", dispatched);
2144         return dispatched;
2145 }
2146
2147 static bool cfq_may_dispatch(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2148 {
2149         unsigned int max_dispatch;
2150
2151         /*
2152          * Drain async requests before we start sync IO
2153          */
2154         if (cfq_should_idle(cfqd, cfqq) && cfqd->rq_in_driver[BLK_RW_ASYNC])
2155                 return false;
2156
2157         /*
2158          * If this is an async queue and we have sync IO in flight, let it wait
2159          */
2160         if (cfqd->sync_flight && !cfq_cfqq_sync(cfqq))
2161                 return false;
2162
2163         max_dispatch = cfqd->cfq_quantum;
2164         if (cfq_class_idle(cfqq))
2165                 max_dispatch = 1;
2166
2167         /*
2168          * Does this cfqq already have too much IO in flight?
2169          */
2170         if (cfqq->dispatched >= max_dispatch) {
2171                 /*
2172                  * idle queue must always only have a single IO in flight
2173                  */
2174                 if (cfq_class_idle(cfqq))
2175                         return false;
2176
2177                 /*
2178                  * We have other queues, don't allow more IO from this one
2179                  */
2180                 if (cfqd->busy_queues > 1)
2181                         return false;
2182
2183                 /*
2184                  * Sole queue user, no limit
2185                  */
2186                 max_dispatch = -1;
2187         }
2188
2189         /*
2190          * Async queues must wait a bit before being allowed dispatch.
2191          * We also ramp up the dispatch depth gradually for async IO,
2192          * based on the last sync IO we serviced
2193          */
2194         if (!cfq_cfqq_sync(cfqq) && cfqd->cfq_latency) {
2195                 unsigned long last_sync = jiffies - cfqd->last_end_sync_rq;
2196                 unsigned int depth;
2197
2198                 depth = last_sync / cfqd->cfq_slice[1];
2199                 if (!depth && !cfqq->dispatched)
2200                         depth = 1;
2201                 if (depth < max_dispatch)
2202                         max_dispatch = depth;
2203         }
2204
2205         /*
2206          * If we're below the current max, allow a dispatch
2207          */
2208         return cfqq->dispatched < max_dispatch;
2209 }
2210
2211 /*
2212  * Dispatch a request from cfqq, moving them to the request queue
2213  * dispatch list.
2214  */
2215 static bool cfq_dispatch_request(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2216 {
2217         struct request *rq;
2218
2219         BUG_ON(RB_EMPTY_ROOT(&cfqq->sort_list));
2220
2221         if (!cfq_may_dispatch(cfqd, cfqq))
2222                 return false;
2223
2224         /*
2225          * follow expired path, else get first next available
2226          */
2227         rq = cfq_check_fifo(cfqq);
2228         if (!rq)
2229                 rq = cfqq->next_rq;
2230
2231         /*
2232          * insert request into driver dispatch list
2233          */
2234         cfq_dispatch_insert(cfqd->queue, rq);
2235
2236         if (!cfqd->active_cic) {
2237                 struct cfq_io_context *cic = RQ_CIC(rq);
2238
2239                 atomic_long_inc(&cic->ioc->refcount);
2240                 cfqd->active_cic = cic;
2241         }
2242
2243         return true;
2244 }
2245
2246 /*
2247  * Find the cfqq that we need to service and move a request from that to the
2248  * dispatch list
2249  */
2250 static int cfq_dispatch_requests(struct request_queue *q, int force)
2251 {
2252         struct cfq_data *cfqd = q->elevator->elevator_data;
2253         struct cfq_queue *cfqq;
2254
2255         if (!cfqd->busy_queues)
2256                 return 0;
2257
2258         if (unlikely(force))
2259                 return cfq_forced_dispatch(cfqd);
2260
2261         cfqq = cfq_select_queue(cfqd);
2262         if (!cfqq)
2263                 return 0;
2264
2265         /*
2266          * Dispatch a request from this cfqq, if it is allowed
2267          */
2268         if (!cfq_dispatch_request(cfqd, cfqq))
2269                 return 0;
2270
2271         cfqq->slice_dispatch++;
2272         cfq_clear_cfqq_must_dispatch(cfqq);
2273
2274         /*
2275          * expire an async queue immediately if it has used up its slice. idle
2276          * queue always expire after 1 dispatch round.
2277          */
2278         if (cfqd->busy_queues > 1 && ((!cfq_cfqq_sync(cfqq) &&
2279             cfqq->slice_dispatch >= cfq_prio_to_maxrq(cfqd, cfqq)) ||
2280             cfq_class_idle(cfqq))) {
2281                 cfqq->slice_end = jiffies + 1;
2282                 cfq_slice_expired(cfqd, 0);
2283         }
2284
2285         cfq_log_cfqq(cfqd, cfqq, "dispatched a request");
2286         return 1;
2287 }
2288
2289 /*
2290  * task holds one reference to the queue, dropped when task exits. each rq
2291  * in-flight on this queue also holds a reference, dropped when rq is freed.
2292  *
2293  * Each cfq queue took a reference on the parent group. Drop it now.
2294  * queue lock must be held here.
2295  */
2296 static void cfq_put_queue(struct cfq_queue *cfqq)
2297 {
2298         struct cfq_data *cfqd = cfqq->cfqd;
2299         struct cfq_group *cfqg;
2300
2301         BUG_ON(atomic_read(&cfqq->ref) <= 0);
2302
2303         if (!atomic_dec_and_test(&cfqq->ref))
2304                 return;
2305
2306         cfq_log_cfqq(cfqd, cfqq, "put_queue");
2307         BUG_ON(rb_first(&cfqq->sort_list));
2308         BUG_ON(cfqq->allocated[READ] + cfqq->allocated[WRITE]);
2309         cfqg = cfqq->cfqg;
2310
2311         if (unlikely(cfqd->active_queue == cfqq)) {
2312                 __cfq_slice_expired(cfqd, cfqq, 0);
2313                 cfq_schedule_dispatch(cfqd);
2314         }
2315
2316         BUG_ON(cfq_cfqq_on_rr(cfqq));
2317         kmem_cache_free(cfq_pool, cfqq);
2318         cfq_put_cfqg(cfqg);
2319 }
2320
2321 /*
2322  * Must always be called with the rcu_read_lock() held
2323  */
2324 static void
2325 __call_for_each_cic(struct io_context *ioc,
2326                     void (*func)(struct io_context *, struct cfq_io_context *))
2327 {
2328         struct cfq_io_context *cic;
2329         struct hlist_node *n;
2330
2331         hlist_for_each_entry_rcu(cic, n, &ioc->cic_list, cic_list)
2332                 func(ioc, cic);
2333 }
2334
2335 /*
2336  * Call func for each cic attached to this ioc.
2337  */
2338 static void
2339 call_for_each_cic(struct io_context *ioc,
2340                   void (*func)(struct io_context *, struct cfq_io_context *))
2341 {
2342         rcu_read_lock();
2343         __call_for_each_cic(ioc, func);
2344         rcu_read_unlock();
2345 }
2346
2347 static void cfq_cic_free_rcu(struct rcu_head *head)
2348 {
2349         struct cfq_io_context *cic;
2350
2351         cic = container_of(head, struct cfq_io_context, rcu_head);
2352
2353         kmem_cache_free(cfq_ioc_pool, cic);
2354         elv_ioc_count_dec(cfq_ioc_count);
2355
2356         if (ioc_gone) {
2357                 /*
2358                  * CFQ scheduler is exiting, grab exit lock and check
2359                  * the pending io context count. If it hits zero,
2360                  * complete ioc_gone and set it back to NULL
2361                  */
2362                 spin_lock(&ioc_gone_lock);
2363                 if (ioc_gone && !elv_ioc_count_read(cfq_ioc_count)) {
2364                         complete(ioc_gone);
2365                         ioc_gone = NULL;
2366                 }
2367                 spin_unlock(&ioc_gone_lock);
2368         }
2369 }
2370
2371 static void cfq_cic_free(struct cfq_io_context *cic)
2372 {
2373         call_rcu(&cic->rcu_head, cfq_cic_free_rcu);
2374 }
2375
2376 static void cic_free_func(struct io_context *ioc, struct cfq_io_context *cic)
2377 {
2378         unsigned long flags;
2379
2380         BUG_ON(!cic->dead_key);
2381
2382         spin_lock_irqsave(&ioc->lock, flags);
2383         radix_tree_delete(&ioc->radix_root, cic->dead_key);
2384         hlist_del_rcu(&cic->cic_list);
2385         spin_unlock_irqrestore(&ioc->lock, flags);
2386
2387         cfq_cic_free(cic);
2388 }
2389
2390 /*
2391  * Must be called with rcu_read_lock() held or preemption otherwise disabled.
2392  * Only two callers of this - ->dtor() which is called with the rcu_read_lock(),
2393  * and ->trim() which is called with the task lock held
2394  */
2395 static void cfq_free_io_context(struct io_context *ioc)
2396 {
2397         /*
2398          * ioc->refcount is zero here, or we are called from elv_unregister(),
2399          * so no more cic's are allowed to be linked into this ioc.  So it
2400          * should be ok to iterate over the known list, we will see all cic's
2401          * since no new ones are added.
2402          */
2403         __call_for_each_cic(ioc, cic_free_func);
2404 }
2405
2406 static void cfq_exit_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq)
2407 {
2408         struct cfq_queue *__cfqq, *next;
2409
2410         if (unlikely(cfqq == cfqd->active_queue)) {
2411                 __cfq_slice_expired(cfqd, cfqq, 0);
2412                 cfq_schedule_dispatch(cfqd);
2413         }
2414
2415         /*
2416          * If this queue was scheduled to merge with another queue, be
2417          * sure to drop the reference taken on that queue (and others in
2418          * the merge chain).  See cfq_setup_merge and cfq_merge_cfqqs.
2419          */
2420         __cfqq = cfqq->new_cfqq;
2421         while (__cfqq) {
2422                 if (__cfqq == cfqq) {
2423                         WARN(1, "cfqq->new_cfqq loop detected\n");
2424                         break;
2425                 }
2426                 next = __cfqq->new_cfqq;
2427                 cfq_put_queue(__cfqq);
2428                 __cfqq = next;
2429         }
2430
2431         cfq_put_queue(cfqq);
2432 }
2433
2434 static void __cfq_exit_single_io_context(struct cfq_data *cfqd,
2435                                          struct cfq_io_context *cic)
2436 {
2437         struct io_context *ioc = cic->ioc;
2438
2439         list_del_init(&cic->queue_list);
2440
2441         /*
2442          * Make sure key == NULL is seen for dead queues
2443          */
2444         smp_wmb();
2445         cic->dead_key = (unsigned long) cic->key;
2446         cic->key = NULL;
2447
2448         if (ioc->ioc_data == cic)
2449                 rcu_assign_pointer(ioc->ioc_data, NULL);
2450
2451         if (cic->cfqq[BLK_RW_ASYNC]) {
2452                 cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_ASYNC]);
2453                 cic->cfqq[BLK_RW_ASYNC] = NULL;
2454         }
2455
2456         if (cic->cfqq[BLK_RW_SYNC]) {
2457                 cfq_exit_cfqq(cfqd, cic->cfqq[BLK_RW_SYNC]);
2458                 cic->cfqq[BLK_RW_SYNC] = NULL;
2459         }
2460 }
2461
2462 static void cfq_exit_single_io_context(struct io_context *ioc,
2463                                        struct cfq_io_context *cic)
2464 {
2465         struct cfq_data *cfqd = cic->key;
2466
2467         if (cfqd) {
2468                 struct request_queue *q = cfqd->queue;
2469                 unsigned long flags;
2470
2471                 spin_lock_irqsave(q->queue_lock, flags);
2472
2473                 /*
2474                  * Ensure we get a fresh copy of the ->key to prevent
2475                  * race between exiting task and queue
2476                  */
2477                 smp_read_barrier_depends();
2478                 if (cic->key)
2479                         __cfq_exit_single_io_context(cfqd, cic);
2480
2481                 spin_unlock_irqrestore(q->queue_lock, flags);
2482         }
2483 }
2484
2485 /*
2486  * The process that ioc belongs to has exited, we need to clean up
2487  * and put the internal structures we have that belongs to that process.
2488  */
2489 static void cfq_exit_io_context(struct io_context *ioc)
2490 {
2491         call_for_each_cic(ioc, cfq_exit_single_io_context);
2492 }
2493
2494 static struct cfq_io_context *
2495 cfq_alloc_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
2496 {
2497         struct cfq_io_context *cic;
2498
2499         cic = kmem_cache_alloc_node(cfq_ioc_pool, gfp_mask | __GFP_ZERO,
2500                                                         cfqd->queue->node);
2501         if (cic) {
2502                 cic->last_end_request = jiffies;
2503                 INIT_LIST_HEAD(&cic->queue_list);
2504                 INIT_HLIST_NODE(&cic->cic_list);
2505                 cic->dtor = cfq_free_io_context;
2506                 cic->exit = cfq_exit_io_context;
2507                 elv_ioc_count_inc(cfq_ioc_count);
2508         }
2509
2510         return cic;
2511 }
2512
2513 static void cfq_init_prio_data(struct cfq_queue *cfqq, struct io_context *ioc)
2514 {
2515         struct task_struct *tsk = current;
2516         int ioprio_class;
2517
2518         if (!cfq_cfqq_prio_changed(cfqq))
2519                 return;
2520
2521         ioprio_class = IOPRIO_PRIO_CLASS(ioc->ioprio);
2522         switch (ioprio_class) {
2523         default:
2524                 printk(KERN_ERR "cfq: bad prio %x\n", ioprio_class);
2525         case IOPRIO_CLASS_NONE:
2526                 /*
2527                  * no prio set, inherit CPU scheduling settings
2528                  */
2529                 cfqq->ioprio = task_nice_ioprio(tsk);
2530                 cfqq->ioprio_class = task_nice_ioclass(tsk);
2531                 break;
2532         case IOPRIO_CLASS_RT:
2533                 cfqq->ioprio = task_ioprio(ioc);
2534                 cfqq->ioprio_class = IOPRIO_CLASS_RT;
2535                 break;
2536         case IOPRIO_CLASS_BE:
2537                 cfqq->ioprio = task_ioprio(ioc);
2538                 cfqq->ioprio_class = IOPRIO_CLASS_BE;
2539                 break;
2540         case IOPRIO_CLASS_IDLE:
2541                 cfqq->ioprio_class = IOPRIO_CLASS_IDLE;
2542                 cfqq->ioprio = 7;
2543                 cfq_clear_cfqq_idle_window(cfqq);
2544                 break;
2545         }
2546
2547         /*
2548          * keep track of original prio settings in case we have to temporarily
2549          * elevate the priority of this queue
2550          */
2551         cfqq->org_ioprio = cfqq->ioprio;
2552         cfqq->org_ioprio_class = cfqq->ioprio_class;
2553         cfq_clear_cfqq_prio_changed(cfqq);
2554 }
2555
2556 static void changed_ioprio(struct io_context *ioc, struct cfq_io_context *cic)
2557 {
2558         struct cfq_data *cfqd = cic->key;
2559         struct cfq_queue *cfqq;
2560         unsigned long flags;
2561
2562         if (unlikely(!cfqd))
2563                 return;
2564
2565         spin_lock_irqsave(cfqd->queue->queue_lock, flags);
2566
2567         cfqq = cic->cfqq[BLK_RW_ASYNC];
2568         if (cfqq) {
2569                 struct cfq_queue *new_cfqq;
2570                 new_cfqq = cfq_get_queue(cfqd, BLK_RW_ASYNC, cic->ioc,
2571                                                 GFP_ATOMIC);
2572                 if (new_cfqq) {
2573                         cic->cfqq[BLK_RW_ASYNC] = new_cfqq;
2574                         cfq_put_queue(cfqq);
2575                 }
2576         }
2577
2578         cfqq = cic->cfqq[BLK_RW_SYNC];
2579         if (cfqq)
2580                 cfq_mark_cfqq_prio_changed(cfqq);
2581
2582         spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
2583 }
2584
2585 static void cfq_ioc_set_ioprio(struct io_context *ioc)
2586 {
2587         call_for_each_cic(ioc, changed_ioprio);
2588         ioc->ioprio_changed = 0;
2589 }
2590
2591 static void cfq_init_cfqq(struct cfq_data *cfqd, struct cfq_queue *cfqq,
2592                           pid_t pid, bool is_sync)
2593 {
2594         RB_CLEAR_NODE(&cfqq->rb_node);
2595         RB_CLEAR_NODE(&cfqq->p_node);
2596         INIT_LIST_HEAD(&cfqq->fifo);
2597
2598         atomic_set(&cfqq->ref, 0);
2599         cfqq->cfqd = cfqd;
2600
2601         cfq_mark_cfqq_prio_changed(cfqq);
2602
2603         if (is_sync) {
2604                 if (!cfq_class_idle(cfqq))
2605                         cfq_mark_cfqq_idle_window(cfqq);
2606                 cfq_mark_cfqq_sync(cfqq);
2607         }
2608         cfqq->pid = pid;
2609 }
2610
2611 #ifdef CONFIG_CFQ_GROUP_IOSCHED
2612 static void changed_cgroup(struct io_context *ioc, struct cfq_io_context *cic)
2613 {
2614         struct cfq_queue *sync_cfqq = cic_to_cfqq(cic, 1);
2615         struct cfq_data *cfqd = cic->key;
2616         unsigned long flags;
2617         struct request_queue *q;
2618
2619         if (unlikely(!cfqd))
2620                 return;
2621
2622         q = cfqd->queue;
2623
2624         spin_lock_irqsave(q->queue_lock, flags);
2625
2626         if (sync_cfqq) {
2627                 /*
2628                  * Drop reference to sync queue. A new sync queue will be
2629                  * assigned in new group upon arrival of a fresh request.
2630                  */
2631                 cfq_log_cfqq(cfqd, sync_cfqq, "changed cgroup");
2632                 cic_set_cfqq(cic, NULL, 1);
2633                 cfq_put_queue(sync_cfqq);
2634         }
2635
2636         spin_unlock_irqrestore(q->queue_lock, flags);
2637 }
2638
2639 static void cfq_ioc_set_cgroup(struct io_context *ioc)
2640 {
2641         call_for_each_cic(ioc, changed_cgroup);
2642         ioc->cgroup_changed = 0;
2643 }
2644 #endif  /* CONFIG_CFQ_GROUP_IOSCHED */
2645
2646 static struct cfq_queue *
2647 cfq_find_alloc_queue(struct cfq_data *cfqd, bool is_sync,
2648                      struct io_context *ioc, gfp_t gfp_mask)
2649 {
2650         struct cfq_queue *cfqq, *new_cfqq = NULL;
2651         struct cfq_io_context *cic;
2652         struct cfq_group *cfqg;
2653
2654 retry:
2655         cfqg = cfq_get_cfqg(cfqd, 1);
2656         cic = cfq_cic_lookup(cfqd, ioc);
2657         /* cic always exists here */
2658         cfqq = cic_to_cfqq(cic, is_sync);
2659
2660         /*
2661          * Always try a new alloc if we fell back to the OOM cfqq
2662          * originally, since it should just be a temporary situation.
2663          */
2664         if (!cfqq || cfqq == &cfqd->oom_cfqq) {
2665                 cfqq = NULL;
2666                 if (new_cfqq) {
2667                         cfqq = new_cfqq;
2668                         new_cfqq = NULL;
2669                 } else if (gfp_mask & __GFP_WAIT) {
2670                         spin_unlock_irq(cfqd->queue->queue_lock);
2671                         new_cfqq = kmem_cache_alloc_node(cfq_pool,
2672                                         gfp_mask | __GFP_ZERO,
2673                                         cfqd->queue->node);
2674                         spin_lock_irq(cfqd->queue->queue_lock);
2675                         if (new_cfqq)
2676                                 goto retry;
2677                 } else {
2678                         cfqq = kmem_cache_alloc_node(cfq_pool,
2679                                         gfp_mask | __GFP_ZERO,
2680                                         cfqd->queue->node);
2681                 }
2682
2683                 if (cfqq) {
2684                         cfq_init_cfqq(cfqd, cfqq, current->pid, is_sync);
2685                         cfq_init_prio_data(cfqq, ioc);
2686                         cfq_link_cfqq_cfqg(cfqq, cfqg);
2687                         cfq_log_cfqq(cfqd, cfqq, "alloced");
2688                 } else
2689                         cfqq = &cfqd->oom_cfqq;
2690         }
2691
2692         if (new_cfqq)
2693                 kmem_cache_free(cfq_pool, new_cfqq);
2694
2695         return cfqq;
2696 }
2697
2698 static struct cfq_queue **
2699 cfq_async_queue_prio(struct cfq_data *cfqd, int ioprio_class, int ioprio)
2700 {
2701         switch (ioprio_class) {
2702         case IOPRIO_CLASS_RT:
2703                 return &cfqd->async_cfqq[0][ioprio];
2704         case IOPRIO_CLASS_BE:
2705                 return &cfqd->async_cfqq[1][ioprio];
2706         case IOPRIO_CLASS_IDLE:
2707                 return &cfqd->async_idle_cfqq;
2708         default:
2709                 BUG();
2710         }
2711 }
2712
2713 static struct cfq_queue *
2714 cfq_get_queue(struct cfq_data *cfqd, bool is_sync, struct io_context *ioc,
2715               gfp_t gfp_mask)
2716 {
2717         const int ioprio = task_ioprio(ioc);
2718         const int ioprio_class = task_ioprio_class(ioc);
2719         struct cfq_queue **async_cfqq = NULL;
2720         struct cfq_queue *cfqq = NULL;
2721
2722         if (!is_sync) {
2723                 async_cfqq = cfq_async_queue_prio(cfqd, ioprio_class, ioprio);
2724                 cfqq = *async_cfqq;
2725         }
2726
2727         if (!cfqq)
2728                 cfqq = cfq_find_alloc_queue(cfqd, is_sync, ioc, gfp_mask);
2729
2730         /*
2731          * pin the queue now that it's allocated, scheduler exit will prune it
2732          */
2733         if (!is_sync && !(*async_cfqq)) {
2734                 atomic_inc(&cfqq->ref);
2735                 *async_cfqq = cfqq;
2736         }
2737
2738         atomic_inc(&cfqq->ref);
2739         return cfqq;
2740 }
2741
2742 /*
2743  * We drop cfq io contexts lazily, so we may find a dead one.
2744  */
2745 static void
2746 cfq_drop_dead_cic(struct cfq_data *cfqd, struct io_context *ioc,
2747                   struct cfq_io_context *cic)
2748 {
2749         unsigned long flags;
2750
2751         WARN_ON(!list_empty(&cic->queue_list));
2752
2753         spin_lock_irqsave(&ioc->lock, flags);
2754
2755         BUG_ON(ioc->ioc_data == cic);
2756
2757         radix_tree_delete(&ioc->radix_root, (unsigned long) cfqd);
2758         hlist_del_rcu(&cic->cic_list);
2759         spin_unlock_irqrestore(&ioc->lock, flags);
2760
2761         cfq_cic_free(cic);
2762 }
2763
2764 static struct cfq_io_context *
2765 cfq_cic_lookup(struct cfq_data *cfqd, struct io_context *ioc)
2766 {
2767         struct cfq_io_context *cic;
2768         unsigned long flags;
2769         void *k;
2770
2771         if (unlikely(!ioc))
2772                 return NULL;
2773
2774         rcu_read_lock();
2775
2776         /*
2777          * we maintain a last-hit cache, to avoid browsing over the tree
2778          */
2779         cic = rcu_dereference(ioc->ioc_data);
2780         if (cic && cic->key == cfqd) {
2781                 rcu_read_unlock();
2782                 return cic;
2783         }
2784
2785         do {
2786                 cic = radix_tree_lookup(&ioc->radix_root, (unsigned long) cfqd);
2787                 rcu_read_unlock();
2788                 if (!cic)
2789                         break;
2790                 /* ->key must be copied to avoid race with cfq_exit_queue() */
2791                 k = cic->key;
2792                 if (unlikely(!k)) {
2793                         cfq_drop_dead_cic(cfqd, ioc, cic);
2794                         rcu_read_lock();
2795                         continue;
2796                 }
2797
2798                 spin_lock_irqsave(&ioc->lock, flags);
2799                 rcu_assign_pointer(ioc->ioc_data, cic);
2800                 spin_unlock_irqrestore(&ioc->lock, flags);
2801                 break;
2802         } while (1);
2803
2804         return cic;
2805 }
2806
2807 /*
2808  * Add cic into ioc, using cfqd as the search key. This enables us to lookup
2809  * the process specific cfq io context when entered from the block layer.
2810  * Also adds the cic to a per-cfqd list, used when this queue is removed.
2811  */
2812 static int cfq_cic_link(struct cfq_data *cfqd, struct io_context *ioc,
2813                         struct cfq_io_context *cic, gfp_t gfp_mask)
2814 {
2815         unsigned long flags;
2816         int ret;
2817
2818         ret = radix_tree_preload(gfp_mask);
2819         if (!ret) {
2820                 cic->ioc = ioc;
2821                 cic->key = cfqd;
2822
2823                 spin_lock_irqsave(&ioc->lock, flags);
2824                 ret = radix_tree_insert(&ioc->radix_root,
2825                                                 (unsigned long) cfqd, cic);
2826                 if (!ret)
2827                         hlist_add_head_rcu(&cic->cic_list, &ioc->cic_list);
2828                 spin_unlock_irqrestore(&ioc->lock, flags);
2829
2830                 radix_tree_preload_end();
2831
2832                 if (!ret) {
2833                         spin_lock_irqsave(cfqd->queue->queue_lock, flags);
2834                         list_add(&cic->queue_list, &cfqd->cic_list);
2835                         spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
2836                 }
2837         }
2838
2839         if (ret)
2840                 printk(KERN_ERR "cfq: cic link failed!\n");
2841
2842         return ret;
2843 }
2844
2845 /*
2846  * Setup general io context and cfq io context. There can be several cfq
2847  * io contexts per general io context, if this process is doing io to more
2848  * than one device managed by cfq.
2849  */
2850 static struct cfq_io_context *
2851 cfq_get_io_context(struct cfq_data *cfqd, gfp_t gfp_mask)
2852 {
2853         struct io_context *ioc = NULL;
2854         struct cfq_io_context *cic;
2855
2856         might_sleep_if(gfp_mask & __GFP_WAIT);
2857
2858         ioc = get_io_context(gfp_mask, cfqd->queue->node);
2859         if (!ioc)
2860                 return NULL;
2861
2862         cic = cfq_cic_lookup(cfqd, ioc);
2863         if (cic)
2864                 goto out;
2865
2866         cic = cfq_alloc_io_context(cfqd, gfp_mask);
2867         if (cic == NULL)
2868                 goto err;
2869
2870         if (cfq_cic_link(cfqd, ioc, cic, gfp_mask))
2871                 goto err_free;
2872
2873 out:
2874         smp_read_barrier_depends();
2875         if (unlikely(ioc->ioprio_changed))
2876                 cfq_ioc_set_ioprio(ioc);
2877
2878 #ifdef CONFIG_CFQ_GROUP_IOSCHED
2879         if (unlikely(ioc->cgroup_changed))
2880                 cfq_ioc_set_cgroup(ioc);
2881 #endif
2882         return cic;
2883 err_free:
2884         cfq_cic_free(cic);
2885 err:
2886         put_io_context(ioc);
2887         return NULL;
2888 }
2889
2890 static void
2891 cfq_update_io_thinktime(struct cfq_data *cfqd, struct cfq_io_context *cic)
2892 {
2893         unsigned long elapsed = jiffies - cic->last_end_request;
2894         unsigned long ttime = min(elapsed, 2UL * cfqd->cfq_slice_idle);
2895
2896         cic->ttime_samples = (7*cic->ttime_samples + 256) / 8;
2897         cic->ttime_total = (7*cic->ttime_total + 256*ttime) / 8;
2898         cic->ttime_mean = (cic->ttime_total + 128) / cic->ttime_samples;
2899 }
2900
2901 static void
2902 cfq_update_io_seektime(struct cfq_data *cfqd, struct cfq_queue *cfqq,
2903                        struct request *rq)
2904 {
2905         sector_t sdist;
2906         u64 total;
2907
2908         if (!cfqq->last_request_pos)
2909                 sdist = 0;
2910         else if (cfqq->last_request_pos < blk_rq_pos(rq))
2911                 sdist = blk_rq_pos(rq) - cfqq->last_request_pos;
2912         else
2913                 sdist = cfqq->last_request_pos - blk_rq_pos(rq);
2914
2915         /*
2916          * Don't allow the seek distance to get too large from the
2917          * odd fragment, pagein, etc
2918          */
2919         if (cfqq->seek_samples <= 60) /* second&third seek */
2920                 sdist = min(sdist, (cfqq->seek_mean * 4) + 2*1024*1024);
2921         else
2922                 sdist = min(sdist, (cfqq->seek_mean * 4) + 2*1024*64);
2923
2924         cfqq->seek_samples = (7*cfqq->seek_samples + 256) / 8;
2925         cfqq->seek_total = (7*cfqq->seek_total + (u64)256*sdist) / 8;
2926         total = cfqq->seek_total + (cfqq->seek_samples/2);
2927         do_div(total, cfqq->seek_samples);
2928         cfqq->seek_mean = (sector_t)total;
2929
2930         /*
2931          * If this cfqq is shared between multiple processes, check to
2932          * make sure that those processes are still issuing I/Os within
2933          * the mean seek distance.  If not, it may be time to break the
2934          * queues apart again.
2935          */
2936         if (cfq_cfqq_coop(cfqq)) {
2937                 if (CFQQ_SEEKY(cfqq) && !cfqq->seeky_start)
2938                         cfqq->seeky_start = jiffies;
2939                 else if (!CFQQ_SEEKY(cfqq))
2940                         cfqq->seeky_start = 0;
2941         }
2942 }
2943
2944 /*
2945  * Disable idle window if the process thinks too long or seeks so much that
2946  * it doesn't matter
2947  */
2948 static void
2949 cfq_update_idle_window(struct cfq_data *cfqd, struct cfq_queue *cfqq,
2950                        struct cfq_io_context *cic)
2951 {
2952         int old_idle, enable_idle;
2953
2954         /*
2955          * Don't idle for async or idle io prio class
2956          */
2957         if (!cfq_cfqq_sync(cfqq) || cfq_class_idle(cfqq))
2958                 return;
2959
2960         enable_idle = old_idle = cfq_cfqq_idle_window(cfqq);
2961
2962         if (cfqq->queued[0] + cfqq->queued[1] >= 4)
2963                 cfq_mark_cfqq_deep(cfqq);
2964
2965         if (!atomic_read(&cic->ioc->nr_tasks) || !cfqd->cfq_slice_idle ||
2966             (!cfq_cfqq_deep(cfqq) && sample_valid(cfqq->seek_samples)
2967              && CFQQ_SEEKY(cfqq)))
2968                 enable_idle = 0;
2969         else if (sample_valid(cic->ttime_samples)) {
2970                 if (cic->ttime_mean > cfqd->cfq_slice_idle)
2971                         enable_idle = 0;
2972                 else
2973                         enable_idle = 1;
2974         }
2975
2976         if (old_idle != enable_idle) {
2977                 cfq_log_cfqq(cfqd, cfqq, "idle=%d", enable_idle);
2978                 if (enable_idle)
2979                         cfq_mark_cfqq_idle_window(cfqq);
2980                 else
2981                         cfq_clear_cfqq_idle_window(cfqq);
2982         }
2983 }
2984
2985 /*
2986  * Check if new_cfqq should preempt the currently active queue. Return 0 for
2987  * no or if we aren't sure, a 1 will cause a preempt.
2988  */
2989 static bool
2990 cfq_should_preempt(struct cfq_data *cfqd, struct cfq_queue *new_cfqq,
2991                    struct request *rq)
2992 {
2993         struct cfq_queue *cfqq;
2994
2995         cfqq = cfqd->active_queue;
2996         if (!cfqq)
2997                 return false;
2998
2999         if (cfq_class_idle(new_cfqq))
3000                 return false;
3001
3002         if (cfq_class_idle(cfqq))
3003                 return true;
3004
3005         /*
3006          * if the new request is sync, but the currently running queue is
3007          * not, let the sync request have priority.
3008          */
3009         if (rq_is_sync(rq) && !cfq_cfqq_sync(cfqq))
3010                 return true;
3011
3012         if (new_cfqq->cfqg != cfqq->cfqg)
3013                 return false;
3014
3015         if (cfq_slice_used(cfqq))
3016                 return true;
3017
3018         /* Allow preemption only if we are idling on sync-noidle tree */
3019         if (cfqd->serving_type == SYNC_NOIDLE_WORKLOAD &&
3020             cfqq_type(new_cfqq) == SYNC_NOIDLE_WORKLOAD &&
3021             new_cfqq->service_tree->count == 2 &&
3022             RB_EMPTY_ROOT(&cfqq->sort_list))
3023                 return true;
3024
3025         /*
3026          * So both queues are sync. Let the new request get disk time if
3027          * it's a metadata request and the current queue is doing regular IO.
3028          */
3029         if (rq_is_meta(rq) && !cfqq->meta_pending)
3030                 return true;
3031
3032         /*
3033          * Allow an RT request to pre-empt an ongoing non-RT cfqq timeslice.
3034          */
3035         if (cfq_class_rt(new_cfqq) && !cfq_class_rt(cfqq))
3036                 return true;
3037
3038         if (!cfqd->active_cic || !cfq_cfqq_wait_request(cfqq))
3039                 return false;
3040
3041         /*
3042          * if this request is as-good as one we would expect from the
3043          * current cfqq, let it preempt
3044          */
3045         if (cfq_rq_close(cfqd, cfqq, rq))
3046                 return true;
3047
3048         return false;
3049 }
3050
3051 /*
3052  * cfqq preempts the active queue. if we allowed preempt with no slice left,
3053  * let it have half of its nominal slice.
3054  */
3055 static void cfq_preempt_queue(struct cfq_data *cfqd, struct cfq_queue *cfqq)
3056 {
3057         cfq_log_cfqq(cfqd, cfqq, "preempt");
3058         cfq_slice_expired(cfqd, 1);
3059
3060         /*
3061          * Put the new queue at the front of the of the current list,
3062          * so we know that it will be selected next.
3063          */
3064         BUG_ON(!cfq_cfqq_on_rr(cfqq));
3065
3066         cfq_service_tree_add(cfqd, cfqq, 1);
3067
3068         cfqq->slice_end = 0;
3069         cfq_mark_cfqq_slice_new(cfqq);
3070 }
3071
3072 /*
3073  * Called when a new fs request (rq) is added (to cfqq). Check if there's
3074  * something we should do about it
3075  */
3076 static void
3077 cfq_rq_enqueued(struct cfq_data *cfqd, struct cfq_queue *cfqq,
3078                 struct request *rq)
3079 {
3080         struct cfq_io_context *cic = RQ_CIC(rq);
3081
3082         cfqd->rq_queued++;
3083         if (rq_is_meta(rq))
3084                 cfqq->meta_pending++;
3085
3086         cfq_update_io_thinktime(cfqd, cic);
3087         cfq_update_io_seektime(cfqd, cfqq, rq);
3088         cfq_update_idle_window(cfqd, cfqq, cic);
3089
3090         cfqq->last_request_pos = blk_rq_pos(rq) + blk_rq_sectors(rq);
3091
3092         if (cfqq == cfqd->active_queue) {
3093                 /*
3094                  * Remember that we saw a request from this process, but
3095                  * don't start queuing just yet. Otherwise we risk seeing lots
3096                  * of tiny requests, because we disrupt the normal plugging
3097                  * and merging. If the request is already larger than a single
3098                  * page, let it rip immediately. For that case we assume that
3099                  * merging is already done. Ditto for a busy system that
3100                  * has other work pending, don't risk delaying until the
3101                  * idle timer unplug to continue working.
3102                  */
3103                 if (cfq_cfqq_wait_request(cfqq)) {
3104                         if (blk_rq_bytes(rq) > PAGE_CACHE_SIZE ||
3105                             cfqd->busy_queues > 1) {
3106                                 del_timer(&cfqd->idle_slice_timer);
3107                                 __blk_run_queue(cfqd->queue);
3108                         } else
3109                                 cfq_mark_cfqq_must_dispatch(cfqq);
3110                 }
3111         } else if (cfq_should_preempt(cfqd, cfqq, rq)) {
3112                 /*
3113                  * not the active queue - expire current slice if it is
3114                  * idle and has expired it's mean thinktime or this new queue
3115                  * has some old slice time left and is of higher priority or
3116                  * this new queue is RT and the current one is BE
3117                  */
3118                 cfq_preempt_queue(cfqd, cfqq);
3119                 __blk_run_queue(cfqd->queue);
3120         }
3121 }
3122
3123 static void cfq_insert_request(struct request_queue *q, struct request *rq)
3124 {
3125         struct cfq_data *cfqd = q->elevator->elevator_data;
3126         struct cfq_queue *cfqq = RQ_CFQQ(rq);
3127
3128         cfq_log_cfqq(cfqd, cfqq, "insert_request");
3129         cfq_init_prio_data(cfqq, RQ_CIC(rq)->ioc);
3130
3131         rq_set_fifo_time(rq, jiffies + cfqd->cfq_fifo_expire[rq_is_sync(rq)]);
3132         list_add_tail(&rq->queuelist, &cfqq->fifo);
3133         cfq_add_rq_rb(rq);
3134
3135         cfq_rq_enqueued(cfqd, cfqq, rq);
3136 }
3137
3138 /*
3139  * Update hw_tag based on peak queue depth over 50 samples under
3140  * sufficient load.
3141  */
3142 static void cfq_update_hw_tag(struct cfq_data *cfqd)
3143 {
3144         struct cfq_queue *cfqq = cfqd->active_queue;
3145
3146         if (rq_in_driver(cfqd) > cfqd->hw_tag_est_depth)
3147                 cfqd->hw_tag_est_depth = rq_in_driver(cfqd);
3148
3149         if (cfqd->hw_tag == 1)
3150                 return;
3151
3152         if (cfqd->rq_queued <= CFQ_HW_QUEUE_MIN &&
3153             rq_in_driver(cfqd) <= CFQ_HW_QUEUE_MIN)
3154                 return;
3155
3156         /*
3157          * If active queue hasn't enough requests and can idle, cfq might not
3158          * dispatch sufficient requests to hardware. Don't zero hw_tag in this
3159          * case
3160          */
3161         if (cfqq && cfq_cfqq_idle_window(cfqq) &&
3162             cfqq->dispatched + cfqq->queued[0] + cfqq->queued[1] <
3163             CFQ_HW_QUEUE_MIN && rq_in_driver(cfqd) < CFQ_HW_QUEUE_MIN)
3164                 return;
3165
3166         if (cfqd->hw_tag_samples++ < 50)
3167                 return;
3168
3169         if (cfqd->hw_tag_est_depth >= CFQ_HW_QUEUE_MIN)
3170                 cfqd->hw_tag = 1;
3171         else
3172                 cfqd->hw_tag = 0;
3173 }
3174
3175 static void cfq_completed_request(struct request_queue *q, struct request *rq)
3176 {
3177         struct cfq_queue *cfqq = RQ_CFQQ(rq);
3178         struct cfq_data *cfqd = cfqq->cfqd;
3179         const int sync = rq_is_sync(rq);
3180         unsigned long now;
3181
3182         now = jiffies;
3183         cfq_log_cfqq(cfqd, cfqq, "complete rqnoidle %d", !!rq_noidle(rq));
3184
3185         cfq_update_hw_tag(cfqd);
3186
3187         WARN_ON(!cfqd->rq_in_driver[sync]);
3188         WARN_ON(!cfqq->dispatched);
3189         cfqd->rq_in_driver[sync]--;
3190         cfqq->dispatched--;
3191
3192         if (cfq_cfqq_sync(cfqq))
3193                 cfqd->sync_flight--;
3194
3195         if (sync) {
3196                 RQ_CIC(rq)->last_end_request = now;
3197                 cfqd->last_end_sync_rq = now;
3198         }
3199
3200         /*
3201          * If this is the active queue, check if it needs to be expired,
3202          * or if we want to idle in case it has no pending requests.
3203          */
3204         if (cfqd->active_queue == cfqq) {
3205                 const bool cfqq_empty = RB_EMPTY_ROOT(&cfqq->sort_list);
3206
3207                 if (cfq_cfqq_slice_new(cfqq)) {
3208                         cfq_set_prio_slice(cfqd, cfqq);
3209                         cfq_clear_cfqq_slice_new(cfqq);
3210                 }
3211                 /*
3212                  * Idling is not enabled on:
3213                  * - expired queues
3214                  * - idle-priority queues
3215                  * - async queues
3216                  * - queues with still some requests queued
3217                  * - when there is a close cooperator
3218                  */
3219                 if (cfq_slice_used(cfqq) || cfq_class_idle(cfqq))
3220                         cfq_slice_expired(cfqd, 1);
3221                 else if (sync && cfqq_empty &&
3222                          !cfq_close_cooperator(cfqd, cfqq)) {
3223                         cfqd->noidle_tree_requires_idle |= !rq_noidle(rq);
3224                         /*
3225                          * Idling is enabled for SYNC_WORKLOAD.
3226                          * SYNC_NOIDLE_WORKLOAD idles at the end of the tree
3227                          * only if we processed at least one !rq_noidle request
3228                          */
3229                         if (cfqd->serving_type == SYNC_WORKLOAD
3230                             || cfqd->noidle_tree_requires_idle)
3231                                 cfq_arm_slice_timer(cfqd);
3232                 }
3233         }
3234
3235         if (!rq_in_driver(cfqd))
3236                 cfq_schedule_dispatch(cfqd);
3237 }
3238
3239 /*
3240  * we temporarily boost lower priority queues if they are holding fs exclusive
3241  * resources. they are boosted to normal prio (CLASS_BE/4)
3242  */
3243 static void cfq_prio_boost(struct cfq_queue *cfqq)
3244 {
3245         if (has_fs_excl()) {
3246                 /*
3247                  * boost idle prio on transactions that would lock out other
3248                  * users of the filesystem
3249                  */
3250                 if (cfq_class_idle(cfqq))
3251                         cfqq->ioprio_class = IOPRIO_CLASS_BE;
3252                 if (cfqq->ioprio > IOPRIO_NORM)
3253                         cfqq->ioprio = IOPRIO_NORM;
3254         } else {
3255                 /*
3256                  * unboost the queue (if needed)
3257                  */
3258                 cfqq->ioprio_class = cfqq->org_ioprio_class;
3259                 cfqq->ioprio = cfqq->org_ioprio;
3260         }
3261 }
3262
3263 static inline int __cfq_may_queue(struct cfq_queue *cfqq)
3264 {
3265         if (cfq_cfqq_wait_request(cfqq) && !cfq_cfqq_must_alloc_slice(cfqq)) {
3266                 cfq_mark_cfqq_must_alloc_slice(cfqq);
3267                 return ELV_MQUEUE_MUST;
3268         }
3269
3270         return ELV_MQUEUE_MAY;
3271 }
3272
3273 static int cfq_may_queue(struct request_queue *q, int rw)
3274 {
3275         struct cfq_data *cfqd = q->elevator->elevator_data;
3276         struct task_struct *tsk = current;
3277         struct cfq_io_context *cic;
3278         struct cfq_queue *cfqq;
3279
3280         /*
3281          * don't force setup of a queue from here, as a call to may_queue
3282          * does not necessarily imply that a request actually will be queued.
3283          * so just lookup a possibly existing queue, or return 'may queue'
3284          * if that fails
3285          */
3286         cic = cfq_cic_lookup(cfqd, tsk->io_context);
3287         if (!cic)
3288                 return ELV_MQUEUE_MAY;
3289
3290         cfqq = cic_to_cfqq(cic, rw_is_sync(rw));
3291         if (cfqq) {
3292                 cfq_init_prio_data(cfqq, cic->ioc);
3293                 cfq_prio_boost(cfqq);
3294
3295                 return __cfq_may_queue(cfqq);
3296         }
3297
3298         return ELV_MQUEUE_MAY;
3299 }
3300
3301 /*
3302  * queue lock held here
3303  */
3304 static void cfq_put_request(struct request *rq)
3305 {
3306         struct cfq_queue *cfqq = RQ_CFQQ(rq);
3307
3308         if (cfqq) {
3309                 const int rw = rq_data_dir(rq);
3310
3311                 BUG_ON(!cfqq->allocated[rw]);
3312                 cfqq->allocated[rw]--;
3313
3314                 put_io_context(RQ_CIC(rq)->ioc);
3315
3316                 rq->elevator_private = NULL;
3317                 rq->elevator_private2 = NULL;
3318
3319                 cfq_put_queue(cfqq);
3320         }
3321 }
3322
3323 static struct cfq_queue *
3324 cfq_merge_cfqqs(struct cfq_data *cfqd, struct cfq_io_context *cic,
3325                 struct cfq_queue *cfqq)
3326 {
3327         cfq_log_cfqq(cfqd, cfqq, "merging with queue %p", cfqq->new_cfqq);
3328         cic_set_cfqq(cic, cfqq->new_cfqq, 1);
3329         cfq_mark_cfqq_coop(cfqq->new_cfqq);
3330         cfq_put_queue(cfqq);
3331         return cic_to_cfqq(cic, 1);
3332 }
3333
3334 static int should_split_cfqq(struct cfq_queue *cfqq)
3335 {
3336         if (cfqq->seeky_start &&
3337             time_after(jiffies, cfqq->seeky_start + CFQQ_COOP_TOUT))
3338                 return 1;
3339         return 0;
3340 }
3341
3342 /*
3343  * Returns NULL if a new cfqq should be allocated, or the old cfqq if this
3344  * was the last process referring to said cfqq.
3345  */
3346 static struct cfq_queue *
3347 split_cfqq(struct cfq_io_context *cic, struct cfq_queue *cfqq)
3348 {
3349         if (cfqq_process_refs(cfqq) == 1) {
3350                 cfqq->seeky_start = 0;
3351                 cfqq->pid = current->pid;
3352                 cfq_clear_cfqq_coop(cfqq);
3353                 return cfqq;
3354         }
3355
3356         cic_set_cfqq(cic, NULL, 1);
3357         cfq_put_queue(cfqq);
3358         return NULL;
3359 }
3360 /*
3361  * Allocate cfq data structures associated with this request.
3362  */
3363 static int
3364 cfq_set_request(struct request_queue *q, struct request *rq, gfp_t gfp_mask)
3365 {
3366         struct cfq_data *cfqd = q->elevator->elevator_data;
3367         struct cfq_io_context *cic;
3368         const int rw = rq_data_dir(rq);
3369         const bool is_sync = rq_is_sync(rq);
3370         struct cfq_queue *cfqq;
3371         unsigned long flags;
3372
3373         might_sleep_if(gfp_mask & __GFP_WAIT);
3374
3375         cic = cfq_get_io_context(cfqd, gfp_mask);
3376
3377         spin_lock_irqsave(q->queue_lock, flags);
3378
3379         if (!cic)
3380                 goto queue_fail;
3381
3382 new_queue:
3383         cfqq = cic_to_cfqq(cic, is_sync);
3384         if (!cfqq || cfqq == &cfqd->oom_cfqq) {
3385                 cfqq = cfq_get_queue(cfqd, is_sync, cic->ioc, gfp_mask);
3386                 cic_set_cfqq(cic, cfqq, is_sync);
3387         } else {
3388                 /*
3389                  * If the queue was seeky for too long, break it apart.
3390                  */
3391                 if (cfq_cfqq_coop(cfqq) && should_split_cfqq(cfqq)) {
3392                         cfq_log_cfqq(cfqd, cfqq, "breaking apart cfqq");
3393                         cfqq = split_cfqq(cic, cfqq);
3394                         if (!cfqq)
3395                                 goto new_queue;
3396                 }
3397
3398                 /*
3399                  * Check to see if this queue is scheduled to merge with
3400                  * another, closely cooperating queue.  The merging of
3401                  * queues happens here as it must be done in process context.
3402                  * The reference on new_cfqq was taken in merge_cfqqs.
3403                  */
3404                 if (cfqq->new_cfqq)
3405                         cfqq = cfq_merge_cfqqs(cfqd, cic, cfqq);
3406         }
3407
3408         cfqq->allocated[rw]++;
3409         atomic_inc(&cfqq->ref);
3410
3411         spin_unlock_irqrestore(q->queue_lock, flags);
3412
3413         rq->elevator_private = cic;
3414         rq->elevator_private2 = cfqq;
3415         return 0;
3416
3417 queue_fail:
3418         if (cic)
3419                 put_io_context(cic->ioc);
3420
3421         cfq_schedule_dispatch(cfqd);
3422         spin_unlock_irqrestore(q->queue_lock, flags);
3423         cfq_log(cfqd, "set_request fail");
3424         return 1;
3425 }
3426
3427 static void cfq_kick_queue(struct work_struct *work)
3428 {
3429         struct cfq_data *cfqd =
3430                 container_of(work, struct cfq_data, unplug_work);
3431         struct request_queue *q = cfqd->queue;
3432
3433         spin_lock_irq(q->queue_lock);
3434         __blk_run_queue(cfqd->queue);
3435         spin_unlock_irq(q->queue_lock);
3436 }
3437
3438 /*
3439  * Timer running if the active_queue is currently idling inside its time slice
3440  */
3441 static void cfq_idle_slice_timer(unsigned long data)
3442 {
3443         struct cfq_data *cfqd = (struct cfq_data *) data;
3444         struct cfq_queue *cfqq;
3445         unsigned long flags;
3446         int timed_out = 1;
3447
3448         cfq_log(cfqd, "idle timer fired");
3449
3450         spin_lock_irqsave(cfqd->queue->queue_lock, flags);
3451
3452         cfqq = cfqd->active_queue;
3453         if (cfqq) {
3454                 timed_out = 0;
3455
3456                 /*
3457                  * We saw a request before the queue expired, let it through
3458                  */
3459                 if (cfq_cfqq_must_dispatch(cfqq))
3460                         goto out_kick;
3461
3462                 /*
3463                  * expired
3464                  */
3465                 if (cfq_slice_used(cfqq))
3466                         goto expire;
3467
3468                 /*
3469                  * only expire and reinvoke request handler, if there are
3470                  * other queues with pending requests
3471                  */
3472                 if (!cfqd->busy_queues)
3473                         goto out_cont;
3474
3475                 /*
3476                  * not expired and it has a request pending, let it dispatch
3477                  */
3478                 if (!RB_EMPTY_ROOT(&cfqq->sort_list))
3479                         goto out_kick;
3480
3481                 /*
3482                  * Queue depth flag is reset only when the idle didn't succeed
3483                  */
3484                 cfq_clear_cfqq_deep(cfqq);
3485         }
3486 expire:
3487         cfq_slice_expired(cfqd, timed_out);
3488 out_kick:
3489         cfq_schedule_dispatch(cfqd);
3490 out_cont:
3491         spin_unlock_irqrestore(cfqd->queue->queue_lock, flags);
3492 }
3493
3494 static void cfq_shutdown_timer_wq(struct cfq_data *cfqd)
3495 {
3496         del_timer_sync(&cfqd->idle_slice_timer);
3497         cancel_work_sync(&cfqd->unplug_work);
3498 }
3499
3500 static void cfq_put_async_queues(struct cfq_data *cfqd)
3501 {
3502         int i;
3503
3504         for (i = 0; i < IOPRIO_BE_NR; i++) {
3505                 if (cfqd->async_cfqq[0][i])
3506                         cfq_put_queue(cfqd->async_cfqq[0][i]);
3507                 if (cfqd->async_cfqq[1][i])
3508                         cfq_put_queue(cfqd->async_cfqq[1][i]);
3509         }
3510
3511         if (cfqd->async_idle_cfqq)
3512                 cfq_put_queue(cfqd->async_idle_cfqq);
3513 }
3514
3515 static void cfq_exit_queue(struct elevator_queue *e)
3516 {
3517         struct cfq_data *cfqd = e->elevator_data;
3518         struct request_queue *q = cfqd->queue;
3519
3520         cfq_shutdown_timer_wq(cfqd);
3521
3522         spin_lock_irq(q->queue_lock);
3523
3524         if (cfqd->active_queue)
3525                 __cfq_slice_expired(cfqd, cfqd->active_queue, 0);
3526
3527         while (!list_empty(&cfqd->cic_list)) {
3528                 struct cfq_io_context *cic = list_entry(cfqd->cic_list.next,
3529                                                         struct cfq_io_context,
3530                                                         queue_list);
3531
3532                 __cfq_exit_single_io_context(cfqd, cic);
3533         }
3534
3535         cfq_put_async_queues(cfqd);
3536         cfq_release_cfq_groups(cfqd);
3537         blkiocg_del_blkio_group(&cfqd->root_group.blkg);
3538
3539         spin_unlock_irq(q->queue_lock);
3540
3541         cfq_shutdown_timer_wq(cfqd);
3542
3543         /* Wait for cfqg->blkg->key accessors to exit their grace periods. */
3544         synchronize_rcu();
3545         kfree(cfqd);
3546 }
3547
3548 static void *cfq_init_queue(struct request_queue *q)
3549 {
3550         struct cfq_data *cfqd;
3551         int i, j;
3552         struct cfq_group *cfqg;
3553         struct cfq_rb_root *st;
3554
3555         cfqd = kmalloc_node(sizeof(*cfqd), GFP_KERNEL | __GFP_ZERO, q->node);
3556         if (!cfqd)
3557                 return NULL;
3558
3559         /* Init root service tree */
3560         cfqd->grp_service_tree = CFQ_RB_ROOT;
3561
3562         /* Init root group */
3563         cfqg = &cfqd->root_group;
3564         for_each_cfqg_st(cfqg, i, j, st)
3565                 *st = CFQ_RB_ROOT;
3566         RB_CLEAR_NODE(&cfqg->rb_node);
3567
3568         /* Give preference to root group over other groups */
3569         cfqg->weight = 2*BLKIO_WEIGHT_DEFAULT;
3570
3571 #ifdef CONFIG_CFQ_GROUP_IOSCHED
3572         /*
3573          * Take a reference to root group which we never drop. This is just
3574          * to make sure that cfq_put_cfqg() does not try to kfree root group
3575          */
3576         atomic_set(&cfqg->ref, 1);
3577         blkiocg_add_blkio_group(&blkio_root_cgroup, &cfqg->blkg, (void *)cfqd,
3578                                         0);
3579 #endif
3580         /*
3581          * Not strictly needed (since RB_ROOT just clears the node and we
3582          * zeroed cfqd on alloc), but better be safe in case someone decides
3583          * to add magic to the rb code
3584          */
3585         for (i = 0; i < CFQ_PRIO_LISTS; i++)
3586                 cfqd->prio_trees[i] = RB_ROOT;
3587
3588         /*
3589          * Our fallback cfqq if cfq_find_alloc_queue() runs into OOM issues.
3590          * Grab a permanent reference to it, so that the normal code flow
3591          * will not attempt to free it.
3592          */
3593         cfq_init_cfqq(cfqd, &cfqd->oom_cfqq, 1, 0);
3594         atomic_inc(&cfqd->oom_cfqq.ref);
3595         cfq_link_cfqq_cfqg(&cfqd->oom_cfqq, &cfqd->root_group);
3596
3597         INIT_LIST_HEAD(&cfqd->cic_list);
3598
3599         cfqd->queue = q;
3600
3601         init_timer(&cfqd->idle_slice_timer);
3602         cfqd->idle_slice_timer.function = cfq_idle_slice_timer;
3603         cfqd->idle_slice_timer.data = (unsigned long) cfqd;
3604
3605         INIT_WORK(&cfqd->unplug_work, cfq_kick_queue);
3606
3607         cfqd->cfq_quantum = cfq_quantum;
3608         cfqd->cfq_fifo_expire[0] = cfq_fifo_expire[0];
3609         cfqd->cfq_fifo_expire[1] = cfq_fifo_expire[1];
3610         cfqd->cfq_back_max = cfq_back_max;
3611         cfqd->cfq_back_penalty = cfq_back_penalty;
3612         cfqd->cfq_slice[0] = cfq_slice_async;
3613         cfqd->cfq_slice[1] = cfq_slice_sync;
3614         cfqd->cfq_slice_async_rq = cfq_slice_async_rq;
3615         cfqd->cfq_slice_idle = cfq_slice_idle;
3616         cfqd->cfq_latency = 1;
3617         cfqd->hw_tag = -1;
3618         cfqd->last_end_sync_rq = jiffies;
3619         return cfqd;
3620 }
3621
3622 static void cfq_slab_kill(void)
3623 {
3624         /*
3625          * Caller already ensured that pending RCU callbacks are completed,
3626          * so we should have no busy allocations at this point.
3627          */
3628         if (cfq_pool)
3629                 kmem_cache_destroy(cfq_pool);
3630         if (cfq_ioc_pool)
3631                 kmem_cache_destroy(cfq_ioc_pool);
3632 }
3633
3634 static int __init cfq_slab_setup(void)
3635 {
3636         cfq_pool = KMEM_CACHE(cfq_queue, 0);
3637         if (!cfq_pool)
3638                 goto fail;
3639
3640         cfq_ioc_pool = KMEM_CACHE(cfq_io_context, 0);
3641         if (!cfq_ioc_pool)
3642                 goto fail;
3643
3644         return 0;
3645 fail:
3646         cfq_slab_kill();
3647         return -ENOMEM;
3648 }
3649
3650 /*
3651  * sysfs parts below -->
3652  */
3653 static ssize_t
3654 cfq_var_show(unsigned int var, char *page)
3655 {
3656         return sprintf(page, "%d\n", var);
3657 }
3658
3659 static ssize_t
3660 cfq_var_store(unsigned int *var, const char *page, size_t count)
3661 {
3662         char *p = (char *) page;
3663
3664         *var = simple_strtoul(p, &p, 10);
3665         return count;
3666 }
3667
3668 #define SHOW_FUNCTION(__FUNC, __VAR, __CONV)                            \
3669 static ssize_t __FUNC(struct elevator_queue *e, char *page)             \
3670 {                                                                       \
3671         struct cfq_data *cfqd = e->elevator_data;                       \
3672         unsigned int __data = __VAR;                                    \
3673         if (__CONV)                                                     \
3674                 __data = jiffies_to_msecs(__data);                      \
3675         return cfq_var_show(__data, (page));                            \
3676 }
3677 SHOW_FUNCTION(cfq_quantum_show, cfqd->cfq_quantum, 0);
3678 SHOW_FUNCTION(cfq_fifo_expire_sync_show, cfqd->cfq_fifo_expire[1], 1);
3679 SHOW_FUNCTION(cfq_fifo_expire_async_show, cfqd->cfq_fifo_expire[0], 1);
3680 SHOW_FUNCTION(cfq_back_seek_max_show, cfqd->cfq_back_max, 0);
3681 SHOW_FUNCTION(cfq_back_seek_penalty_show, cfqd->cfq_back_penalty, 0);
3682 SHOW_FUNCTION(cfq_slice_idle_show, cfqd->cfq_slice_idle, 1);
3683 SHOW_FUNCTION(cfq_slice_sync_show, cfqd->cfq_slice[1], 1);
3684 SHOW_FUNCTION(cfq_slice_async_show, cfqd->cfq_slice[0], 1);
3685 SHOW_FUNCTION(cfq_slice_async_rq_show, cfqd->cfq_slice_async_rq, 0);
3686 SHOW_FUNCTION(cfq_low_latency_show, cfqd->cfq_latency, 0);
3687 #undef SHOW_FUNCTION
3688
3689 #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV)                 \
3690 static ssize_t __FUNC(struct elevator_queue *e, const char *page, size_t count) \
3691 {                                                                       \
3692         struct cfq_data *cfqd = e->elevator_data;                       \
3693         unsigned int __data;                                            \
3694         int ret = cfq_var_store(&__data, (page), count);                \
3695         if (__data < (MIN))                                             \
3696                 __data = (MIN);                                         \
3697         else if (__data > (MAX))                                        \
3698                 __data = (MAX);                                         \
3699         if (__CONV)                                                     \
3700                 *(__PTR) = msecs_to_jiffies(__data);                    \
3701         else                                                            \
3702                 *(__PTR) = __data;                                      \
3703         return ret;                                                     \
3704 }
3705 STORE_FUNCTION(cfq_quantum_store, &cfqd->cfq_quantum, 1, UINT_MAX, 0);
3706 STORE_FUNCTION(cfq_fifo_expire_sync_store, &cfqd->cfq_fifo_expire[1], 1,
3707                 UINT_MAX, 1);
3708 STORE_FUNCTION(cfq_fifo_expire_async_store, &cfqd->cfq_fifo_expire[0], 1,
3709                 UINT_MAX, 1);
3710 STORE_FUNCTION(cfq_back_seek_max_store, &cfqd->cfq_back_max, 0, UINT_MAX, 0);
3711 STORE_FUNCTION(cfq_back_seek_penalty_store, &cfqd->cfq_back_penalty, 1,
3712                 UINT_MAX, 0);
3713 STORE_FUNCTION(cfq_slice_idle_store, &cfqd->cfq_slice_idle, 0, UINT_MAX, 1);
3714 STORE_FUNCTION(cfq_slice_sync_store, &cfqd->cfq_slice[1], 1, UINT_MAX, 1);
3715 STORE_FUNCTION(cfq_slice_async_store, &cfqd->cfq_slice[0], 1, UINT_MAX, 1);
3716 STORE_FUNCTION(cfq_slice_async_rq_store, &cfqd->cfq_slice_async_rq, 1,
3717                 UINT_MAX, 0);
3718 STORE_FUNCTION(cfq_low_latency_store, &cfqd->cfq_latency, 0, 1, 0);
3719 #undef STORE_FUNCTION
3720
3721 #define CFQ_ATTR(name) \
3722         __ATTR(name, S_IRUGO|S_IWUSR, cfq_##name##_show, cfq_##name##_store)
3723
3724 static struct elv_fs_entry cfq_attrs[] = {
3725         CFQ_ATTR(quantum),
3726         CFQ_ATTR(fifo_expire_sync),
3727         CFQ_ATTR(fifo_expire_async),
3728         CFQ_ATTR(back_seek_max),
3729         CFQ_ATTR(back_seek_penalty),
3730         CFQ_ATTR(slice_sync),
3731         CFQ_ATTR(slice_async),
3732         CFQ_ATTR(slice_async_rq),
3733         CFQ_ATTR(slice_idle),
3734         CFQ_ATTR(low_latency),
3735         __ATTR_NULL
3736 };
3737
3738 static struct elevator_type iosched_cfq = {
3739         .ops = {
3740                 .elevator_merge_fn =            cfq_merge,
3741                 .elevator_merged_fn =           cfq_merged_request,
3742                 .elevator_merge_req_fn =        cfq_merged_requests,
3743                 .elevator_allow_merge_fn =      cfq_allow_merge,
3744                 .elevator_dispatch_fn =         cfq_dispatch_requests,
3745                 .elevator_add_req_fn =          cfq_insert_request,
3746                 .elevator_activate_req_fn =     cfq_activate_request,
3747                 .elevator_deactivate_req_fn =   cfq_deactivate_request,
3748                 .elevator_queue_empty_fn =      cfq_queue_empty,
3749                 .elevator_completed_req_fn =    cfq_completed_request,
3750                 .elevator_former_req_fn =       elv_rb_former_request,
3751                 .elevator_latter_req_fn =       elv_rb_latter_request,
3752                 .elevator_set_req_fn =          cfq_set_request,
3753                 .elevator_put_req_fn =          cfq_put_request,
3754                 .elevator_may_queue_fn =        cfq_may_queue,
3755                 .elevator_init_fn =             cfq_init_queue,
3756                 .elevator_exit_fn =             cfq_exit_queue,
3757                 .trim =                         cfq_free_io_context,
3758         },
3759         .elevator_attrs =       cfq_attrs,
3760         .elevator_name =        "cfq",
3761         .elevator_owner =       THIS_MODULE,
3762 };
3763
3764 static int __init cfq_init(void)
3765 {
3766         /*
3767          * could be 0 on HZ < 1000 setups
3768          */
3769         if (!cfq_slice_async)
3770                 cfq_slice_async = 1;
3771         if (!cfq_slice_idle)
3772                 cfq_slice_idle = 1;
3773
3774         if (cfq_slab_setup())
3775                 return -ENOMEM;
3776
3777         elv_register(&iosched_cfq);
3778
3779         return 0;
3780 }
3781
3782 static void __exit cfq_exit(void)
3783 {
3784         DECLARE_COMPLETION_ONSTACK(all_gone);
3785         elv_unregister(&iosched_cfq);
3786         ioc_gone = &all_gone;
3787         /* ioc_gone's update must be visible before reading ioc_count */
3788         smp_wmb();
3789
3790         /*
3791          * this also protects us from entering cfq_slab_kill() with
3792          * pending RCU callbacks
3793          */
3794         if (elv_ioc_count_read(cfq_ioc_count))
3795                 wait_for_completion(&all_gone);
3796         cfq_slab_kill();
3797 }
3798
3799 module_init(cfq_init);
3800 module_exit(cfq_exit);
3801
3802 MODULE_AUTHOR("Jens Axboe");
3803 MODULE_LICENSE("GPL");
3804 MODULE_DESCRIPTION("Completely Fair Queueing IO scheduler");