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