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

Archive Download this file



interactive