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