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