+ * Must be called with the queue_lock held.
+ */
+static int cfqq_process_refs(struct cfq_queue *cfqq)
+{
+ int process_refs, io_refs;
+
+ io_refs = cfqq->allocated[READ] + cfqq->allocated[WRITE];
+ process_refs = atomic_read(&cfqq->ref) - io_refs;
+ BUG_ON(process_refs < 0);
+ return process_refs;
+}
+
+static void cfq_setup_merge(struct cfq_queue *cfqq, struct cfq_queue *new_cfqq)
+{
+ int process_refs, new_process_refs;
+ struct cfq_queue *__cfqq;
+
+ /* Avoid a circular list and skip interim queue merges */
+ while ((__cfqq = new_cfqq->new_cfqq)) {
+ if (__cfqq == cfqq)
+ return;
+ new_cfqq = __cfqq;
+ }
+
+ process_refs = cfqq_process_refs(cfqq);
+ /*
+ * If the process for the cfqq has gone away, there is no
+ * sense in merging the queues.
+ */
+ if (process_refs == 0)
+ return;
+
+ /*
+ * Merge in the direction of the lesser amount of work.
+ */
+ new_process_refs = cfqq_process_refs(new_cfqq);
+ if (new_process_refs >= process_refs) {
+ cfqq->new_cfqq = new_cfqq;
+ atomic_add(process_refs, &new_cfqq->ref);
+ } else {
+ new_cfqq->new_cfqq = cfqq;
+ atomic_add(new_process_refs, &cfqq->ref);
+ }
+}
+
+static enum wl_type_t cfq_choose_wl(struct cfq_data *cfqd, enum wl_prio_t prio,
+ bool prio_changed)
+{
+ struct cfq_queue *queue;
+ int i;
+ bool key_valid = false;
+ unsigned long lowest_key = 0;
+ enum wl_type_t cur_best = SYNC_NOIDLE_WORKLOAD;
+
+ if (prio_changed) {
+ /*
+ * When priorities switched, we prefer starting
+ * from SYNC_NOIDLE (first choice), or just SYNC
+ * over ASYNC
+ */
+ if (service_tree_for(prio, cur_best, cfqd)->count)
+ return cur_best;
+ cur_best = SYNC_WORKLOAD;
+ if (service_tree_for(prio, cur_best, cfqd)->count)
+ return cur_best;
+
+ return ASYNC_WORKLOAD;
+ }
+
+ for (i = 0; i < 3; ++i) {
+ /* otherwise, select the one with lowest rb_key */
+ queue = cfq_rb_first(service_tree_for(prio, i, cfqd));
+ if (queue &&
+ (!key_valid || time_before(queue->rb_key, lowest_key))) {
+ lowest_key = queue->rb_key;
+ cur_best = i;
+ key_valid = true;
+ }
+ }
+
+ return cur_best;
+}
+
+static void choose_service_tree(struct cfq_data *cfqd)
+{
+ enum wl_prio_t previous_prio = cfqd->serving_prio;
+ bool prio_changed;
+ unsigned slice;
+ unsigned count;
+
+ /* Choose next priority. RT > BE > IDLE */
+ if (cfq_busy_queues_wl(RT_WORKLOAD, cfqd))
+ cfqd->serving_prio = RT_WORKLOAD;
+ else if (cfq_busy_queues_wl(BE_WORKLOAD, cfqd))
+ cfqd->serving_prio = BE_WORKLOAD;
+ else {
+ cfqd->serving_prio = IDLE_WORKLOAD;
+ cfqd->workload_expires = jiffies + 1;
+ return;
+ }
+
+ /*
+ * For RT and BE, we have to choose also the type
+ * (SYNC, SYNC_NOIDLE, ASYNC), and to compute a workload
+ * expiration time
+ */
+ prio_changed = (cfqd->serving_prio != previous_prio);
+ count = service_tree_for(cfqd->serving_prio, cfqd->serving_type, cfqd)
+ ->count;
+
+ /*
+ * If priority didn't change, check workload expiration,
+ * and that we still have other queues ready
+ */
+ if (!prio_changed && count &&
+ !time_after(jiffies, cfqd->workload_expires))
+ return;
+
+ /* otherwise select new workload type */
+ cfqd->serving_type =
+ cfq_choose_wl(cfqd, cfqd->serving_prio, prio_changed);
+ count = service_tree_for(cfqd->serving_prio, cfqd->serving_type, cfqd)
+ ->count;
+
+ /*
+ * the workload slice is computed as a fraction of target latency
+ * proportional to the number of queues in that workload, over
+ * all the queues in the same priority class
+ */
+ slice = cfq_target_latency * count /
+ max_t(unsigned, cfqd->busy_queues_avg[cfqd->serving_prio],
+ cfq_busy_queues_wl(cfqd->serving_prio, cfqd));
+
+ if (cfqd->serving_type == ASYNC_WORKLOAD)
+ /* async workload slice is scaled down according to
+ * the sync/async slice ratio. */
+ slice = slice * cfqd->cfq_slice[0] / cfqd->cfq_slice[1];
+ else
+ /* sync workload slice is at least 2 * cfq_slice_idle */
+ slice = max(slice, 2 * cfqd->cfq_slice_idle);
+
+ slice = max_t(unsigned, slice, CFQ_MIN_TT);
+ cfqd->workload_expires = jiffies + slice;
+ cfqd->noidle_tree_requires_idle = false;
+}
+
+/*