Changes to series and rx51_defconfig file for BFQ

[kernel-bfs] / kernel-bfs-2.6.28 / debian / patches / block-switch-from-BFQ-for-2.6.28-to-BFQ-v1.patch

diff -uprN linux-2.6.28/block/bfq-cgroup.c linux-2.6.28.new/block/bfq-cgroup.c
--- linux-2.6.28/block/bfq-cgroup.c     2011-06-13 21:41:23.758108202 +0200
+++ linux-2.6.28.new/block/bfq-cgroup.c 2011-06-13 21:41:41.631928601 +0200
@@ -6,10 +6,13 @@
  *
  * Copyright (C) 2008 Fabio Checconi <fabio@gandalf.sssup.it>
  *                   Paolo Valente <paolo.valente@unimore.it>
+ *
+ * Licensed under the GPL-2 as detailed in the accompanying COPYING.BFQ file.
  */
 
 #ifdef CONFIG_CGROUP_BFQIO
 static struct bfqio_cgroup bfqio_root_cgroup = {
+       .weight = BFQ_DEFAULT_GRP_WEIGHT,
        .ioprio = BFQ_DEFAULT_GRP_IOPRIO,
        .ioprio_class = BFQ_DEFAULT_GRP_CLASS,
 };
@@ -17,6 +20,8 @@ static struct bfqio_cgroup bfqio_root_cg
 static inline void bfq_init_entity(struct bfq_entity *entity,
                                   struct bfq_group *bfqg)
 {
+       entity->weight = entity->new_weight;
+       entity->orig_weight = entity->new_weight;
        entity->ioprio = entity->new_ioprio;
        entity->ioprio_class = entity->new_ioprio_class;
        entity->parent = bfqg->my_entity;
@@ -54,6 +59,8 @@ static inline void bfq_group_init_entity
 {
        struct bfq_entity *entity = &bfqg->entity;
 
+       entity->weight = entity->new_weight = bgrp->weight;
+       entity->orig_weight = entity->new_weight;
        entity->ioprio = entity->new_ioprio = bgrp->ioprio;
        entity->ioprio_class = entity->new_ioprio_class = bgrp->ioprio_class;
        entity->ioprio_changed = 1;
@@ -301,6 +308,9 @@ static struct bfq_group *__bfq_cic_chang
 
                if (entity->sched_data != &bfqg->sched_data) {
                        cic_set_bfqq(cic, NULL, 0);
+                       bfq_log_bfqq(bfqd, async_bfqq,
+                                    "cic_change_group: %p %d",
+                                    async_bfqq, async_bfqq->ref);
                        bfq_put_queue(async_bfqq);
                }
        }
@@ -453,6 +463,7 @@ static void bfq_disconnect_groups(struct
        struct hlist_node *pos, *n;
        struct bfq_group *bfqg;
 
+       bfq_log(bfqd, "disconnect_groups beginning") ;
        hlist_for_each_entry_safe(bfqg, pos, n, &bfqd->group_list, bfqd_node) {
                hlist_del(&bfqg->bfqd_node);
 
@@ -466,6 +477,9 @@ static void bfq_disconnect_groups(struct
                 * to the list.
                 */
                rcu_assign_pointer(bfqg->bfqd, NULL);
+
+               bfq_log(bfqd, "disconnect_groups: put async for group %p",
+                       bfqg) ;
                bfq_put_async_queues(bfqd, bfqg);
        }
 }
@@ -475,6 +489,8 @@ static inline void bfq_free_root_group(s
        struct bfqio_cgroup *bgrp = &bfqio_root_cgroup;
        struct bfq_group *bfqg = bfqd->root_group;
 
+       bfq_put_async_queues(bfqd, bfqg);
+
        spin_lock_irq(&bgrp->lock);
        hlist_del_rcu(&bfqg->group_node);
        spin_unlock_irq(&bgrp->lock);
@@ -529,6 +545,7 @@ static u64 bfqio_cgroup_##__VAR##_read(s
        return ret;                                                     \
 }
 
+SHOW_FUNCTION(weight);
 SHOW_FUNCTION(ioprio);
 SHOW_FUNCTION(ioprio_class);
 #undef SHOW_FUNCTION
@@ -551,9 +568,9 @@ static int bfqio_cgroup_##__VAR##_write(
        bgrp = cgroup_to_bfqio(cgroup);                                 \
                                                                        \
        spin_lock_irq(&bgrp->lock);                                     \
-       bgrp->__VAR = (unsigned char)val;                               \
+       bgrp->__VAR = (unsigned short)val;                              \
        hlist_for_each_entry(bfqg, n, &bgrp->group_data, group_node) {  \
-               bfqg->entity.new_##__VAR = (unsigned char)val;          \
+               bfqg->entity.new_##__VAR = (unsigned short)val;         \
                smp_wmb();                                              \
                bfqg->entity.ioprio_changed = 1;                        \
        }                                                               \
@@ -564,12 +581,18 @@ static int bfqio_cgroup_##__VAR##_write(
        return 0;                                                       \
 }
 
+STORE_FUNCTION(weight, BFQ_MIN_WEIGHT, BFQ_MAX_WEIGHT);
 STORE_FUNCTION(ioprio, 0, IOPRIO_BE_NR - 1);
 STORE_FUNCTION(ioprio_class, IOPRIO_CLASS_RT, IOPRIO_CLASS_IDLE);
 #undef STORE_FUNCTION
 
 static struct cftype bfqio_files[] = {
        {
+               .name = "weight",
+               .read_u64 = bfqio_cgroup_weight_read,
+               .write_u64 = bfqio_cgroup_weight_write,
+       },
+       {
                .name = "ioprio",
                .read_u64 = bfqio_cgroup_ioprio_read,
                .write_u64 = bfqio_cgroup_ioprio_write,
@@ -697,6 +720,8 @@ struct cgroup_subsys bfqio_subsys = {
 static inline void bfq_init_entity(struct bfq_entity *entity,
                                   struct bfq_group *bfqg)
 {
+       entity->weight = entity->new_weight;
+       entity->orig_weight = entity->new_weight;
        entity->ioprio = entity->new_ioprio;
        entity->ioprio_class = entity->new_ioprio_class;
        entity->sched_data = &bfqg->sched_data;
diff -uprN linux-2.6.28/block/bfq-iosched.c linux-2.6.28.new/block/bfq-iosched.c
--- linux-2.6.28/block/bfq-iosched.c    2011-06-13 21:41:23.766107399 +0200
+++ linux-2.6.28.new/block/bfq-iosched.c        2011-06-13 21:42:46.519829365 +0200
@@ -7,23 +7,36 @@
  * Copyright (C) 2008 Fabio Checconi <fabio@gandalf.sssup.it>
  *                   Paolo Valente <paolo.valente@unimore.it>
  *
- * BFQ is a proportional share disk scheduling algorithm based on CFQ,
- * that uses the B-WF2Q+ internal scheduler to assign budgets (i.e.,
- * slices in the service domain) to the tasks accessing the disk.  It
- * has been introduced in [1], where the interested reader can find an
- * accurate description of the algorithm, the guarantees it provides
- * and their formal proofs.  With respect to the algorithm presented
- * in the paper, this implementation adds a timeout to limit the maximum
- * time a queue can spend to complete its assigned budget, and a
- * hierarchical extension, based on H-WF2Q+.
+ * Licensed under the GPL-2 as detailed in the accompanying COPYING.BFQ file.
+ *
+ * BFQ is a proportional share disk scheduling algorithm based on the
+ * slice-by-slice service scheme of CFQ. But BFQ assigns budgets,
+ * measured in number of sectors, to tasks instead of time slices.
+ * The disk is not granted to the active task for a given time slice,
+ * but until it has exahusted its assigned budget.  This change from
+ * the time to the service domain allows BFQ to distribute the disk
+ * bandwidth among tasks as desired, without any distortion due to
+ * ZBR, workload fluctuations or other factors. BFQ uses an ad hoc
+ * internal scheduler, called B-WF2Q+, to schedule tasks according to
+ * their budgets.  Thanks to this accurate scheduler, BFQ can afford
+ * to assign high budgets to disk-bound non-seeky tasks (to boost the
+ * throughput), and yet guarantee low latencies to interactive and
+ * soft real-time applications.
+ *
+ * BFQ has been introduced in [1], where the interested reader can
+ * find an accurate description of the algorithm, the bandwidth
+ * distribution and latency guarantees it provides, plus formal proofs
+ * of all the properties.  With respect to the algorithm presented in
+ * the paper, this implementation adds several little heuristics, and
+ * a hierarchical extension, based on H-WF2Q+.
  *
  * B-WF2Q+ is based on WF2Q+, that is described in [2], together with
  * H-WF2Q+, while the augmented tree used to implement B-WF2Q+ with O(log N)
  * complexity derives from the one introduced with EEVDF in [3].
  *
  * [1] P. Valente and F. Checconi, ``High Throughput Disk Scheduling
- *     with Deterministic Guarantees on Bandwidth Distribution,'' to be
- *     published.
+ *     with Deterministic Guarantees on Bandwidth Distribution,'' to appear
+ *     on IEEE Transactions on Computer.
  *
  *     http://algo.ing.unimo.it/people/paolo/disk_sched/bfq.pdf
  *
@@ -40,6 +53,7 @@
  *     http://www.cs.berkeley.edu/~istoica/papers/eevdf-tr-95.pdf
  */
 #include <linux/module.h>
+#include <linux/slab.h>
 #include <linux/blkdev.h>
 #include <linux/cgroup.h>
 #include <linux/elevator.h>
@@ -47,26 +61,33 @@
 #include <linux/ioprio.h>
 #include "bfq.h"
 
-/* Max nr of dispatches in one round of service. */
+/* Max number of dispatches in one round of service. */
 static const int bfq_quantum = 4;
 
-/* Expiration time of each request (jiffies). */
+/* Expiration time of sync (0) and async (1) requests, in jiffies. */
 static const int bfq_fifo_expire[2] = { HZ / 4, HZ / 8 };
 
 /* Maximum backwards seek, in KiB. */
 static const int bfq_back_max = 16 * 1024;
 
-/* Penalty of a backwards seek. */
+/* Penalty of a backwards seek, in number of sectors. */
 static const int bfq_back_penalty = 2;
 
-/* Idling period duration (jiffies). */
+/* Idling period duration, in jiffies. */
 static int bfq_slice_idle = HZ / 125;
 
-/* Default maximum budget values (sectors). */
-static const int bfq_max_budget = 16 * 1024;
+/* Default maximum budget values, in sectors and number of requests. */
+static const int bfq_default_max_budget = 16 * 1024;
 static const int bfq_max_budget_async_rq = 4;
 
-/* Default timeout values (jiffies), approximating CFQ defaults. */
+/*
+ * Async to sync throughput distribution is controlled as follows:
+ * when an async request is served, the entity is charged the number
+ * of sectors of the request, multipled by the factor below
+ */
+static const int bfq_async_charge_factor = 10;
+
+/* Default timeout values, in jiffies, approximating CFQ defaults. */
 static const int bfq_timeout_sync = HZ / 8;
 static int bfq_timeout_async = HZ / 25;
 
@@ -84,8 +105,7 @@ static DEFINE_SPINLOCK(bfq_ioc_gone_lock
 #define BFQ_HW_QUEUE_THRESHOLD 4
 #define BFQ_HW_QUEUE_SAMPLES   32
 
-/* Budget feedback step. */
-#define BFQ_BUDGET_STEP                128
+#define BFQQ_SEEKY(bfqq) ((bfqq)->seek_mean > (8 * 1024))
 
 /* Min samples used for peak rate estimation (for autotuning). */
 #define BFQ_PEAK_RATE_SAMPLES  32
@@ -104,15 +124,10 @@ static DEFINE_SPINLOCK(bfq_ioc_gone_lock
 #include "bfq-sched.c"
 #include "bfq-cgroup.c"
 
-static inline int bfq_class_idle(struct bfq_queue *bfqq)
-{
-       return bfqq->entity.ioprio_class == IOPRIO_CLASS_IDLE;
-}
+#define bfq_class_idle(cfqq)   ((bfqq)->entity.ioprio_class ==\
+                                IOPRIO_CLASS_IDLE)
 
-static inline int bfq_sample_valid(int samples)
-{
-       return samples > 80;
-}
+#define bfq_sample_valid(samples)      ((samples) > 80)
 
 /*
  * We regard a request as SYNC, if either it's a read or has the SYNC bit
@@ -180,7 +195,7 @@ static struct request *bfq_choose_req(st
        last = bfqd->last_position;
 
        /*
-        * by definition, 1KiB is 2 sectors
+        * By definition, 1KiB is 2 sectors.
         */
        back_max = bfqd->bfq_back_max * 2;
 
@@ -282,17 +297,24 @@ static void bfq_del_rq_rb(struct request
                bfq_del_bfqq_busy(bfqd, bfqq, 1);
 }
 
+/* see the definition of bfq_async_charge_factor for details */
+static inline unsigned long bfq_serv_to_charge(struct request *rq,
+                                              struct bfq_queue *bfqq)
+{
+       return rq->hard_nr_sectors *
+               (1 + ((!bfq_bfqq_sync(bfqq)) * bfq_async_charge_factor));
+}
+
 /**
  * bfq_updated_next_req - update the queue after a new next_rq selection.
  * @bfqd: the device data the queue belongs to.
  * @bfqq: the queue to update.
  *
- * Whenever the first request of a queue changes we try to allocate it
- * enough service (if it has grown), or to anticipate its finish time
- * (if it has shrinked), to reduce the time it has to wait, still taking
- * into account the queue budget.  We try to avoid the queue having not
- * enough service allocated for its first request, thus having to go
- * through two dispatch rounds to actually dispatch the request.
+ * If the first request of a queue changes we make sure that the queue
+ * has enough budget to serve at least its first request (if the
+ * request has grown).  We do this because if the queue has not enough
+ * budget for its first request, it has to go through two dispatch
+ * rounds to actually get it dispatched.
  */
 static void bfq_updated_next_req(struct bfq_data *bfqd,
                                 struct bfq_queue *bfqq)
@@ -300,7 +322,7 @@ static void bfq_updated_next_req(struct 
        struct bfq_entity *entity = &bfqq->entity;
        struct bfq_service_tree *st = bfq_entity_service_tree(entity);
        struct request *next_rq = bfqq->next_rq;
-       bfq_service_t new_budget;
+       unsigned long new_budget;
 
        if (next_rq == NULL)
                return;
@@ -315,9 +337,10 @@ static void bfq_updated_next_req(struct 
        BUG_ON(entity->tree != &st->active);
        BUG_ON(entity == entity->sched_data->active_entity);
 
-       new_budget = max(bfqq->max_budget, next_rq->hard_nr_sectors);
+       new_budget = max_t(unsigned long, bfqq->max_budget,
+                          bfq_serv_to_charge(next_rq, bfqq));
        entity->budget = new_budget;
-       bfq_log_bfqq(bfqd, bfqq, "budget=%lu", new_budget);
+       bfq_log_bfqq(bfqd, bfqq, "updated next rq: new budget %lu", new_budget);
        bfq_activate_bfqq(bfqd, bfqq);
 }
 
@@ -328,6 +351,7 @@ static void bfq_add_rq_rb(struct request
        struct bfq_data *bfqd = bfqq->bfqd;
        struct request *__alias, *next_rq;
 
+       bfq_log_bfqq(bfqd, bfqq, "add_rq_rb %d", rq_is_sync(rq));
        bfqq->queued[rq_is_sync(rq)]++;
        bfqd->queued++;
 
@@ -339,15 +363,33 @@ static void bfq_add_rq_rb(struct request
                bfq_dispatch_insert(bfqd->queue, __alias);
 
        /*
-        * check if this request is a better next-serve candidate
+        * Check if this request is a better next-serve candidate.
         */
        next_rq = bfq_choose_req(bfqd, bfqq->next_rq, rq);
        BUG_ON(next_rq == NULL);
        bfqq->next_rq = next_rq;
 
        if (!bfq_bfqq_busy(bfqq)) {
-               entity->budget = max(bfqq->max_budget,
-                                    next_rq->hard_nr_sectors);
+               entity->budget = max_t(unsigned long, bfqq->max_budget,
+                                      bfq_serv_to_charge(next_rq, bfqq));
+
+               /*
+                * If the queue is not being boosted and has been idle
+                * for enough time, start a boosting period
+                */
+               if (bfqd->low_latency && bfqq->high_weight_budget == 0) {
+                       if (bfqq->last_activation_time + BFQ_MIN_ACT_INTERVAL <
+                           jiffies_to_msecs(jiffies)) {
+                               bfqq->high_weight_budget = BFQ_BOOST_BUDGET;
+                               entity->ioprio_changed = 1;
+                               bfq_log_bfqq(bfqd, bfqq,
+                                            "wboost starting at %lu msec",
+                                            bfqq->last_activation_time);
+                       }
+                       bfqq->last_activation_time =
+                               jiffies_to_msecs(jiffies);
+               }
+
                bfq_add_bfqq_busy(bfqd, bfqq);
        } else
                bfq_updated_next_req(bfqd, bfqq);
@@ -446,7 +488,7 @@ static void bfq_merged_requests(struct r
                                struct request *next)
 {
        /*
-        * reposition in fifo if next is older than rq
+        * Reposition in fifo if next is older than rq.
         */
        if (!list_empty(&rq->queuelist) && !list_empty(&next->queuelist) &&
            time_before(next->start_time, rq->start_time))
@@ -475,10 +517,7 @@ static int bfq_allow_merge(struct reques
                return 0;
 
        bfqq = cic_to_bfqq(cic, bfq_bio_sync(bio));
-       if (bfqq == RQ_BFQQ(rq))
-               return 1;
-
-       return 0;
+       return bfqq == RQ_BFQQ(rq);
 }
 
 static void __bfq_set_active_queue(struct bfq_data *bfqd,
@@ -489,9 +528,10 @@ static void __bfq_set_active_queue(struc
                bfq_mark_bfqq_budget_new(bfqq);
                bfq_clear_bfqq_fifo_expire(bfqq);
 
-               bfqq->budgets_assigned = (bfqq->budgets_assigned*7 + 256) / 8;
+               bfqd->budgets_assigned = (bfqd->budgets_assigned*7 + 256) / 8;
 
-               bfq_log_bfqq(bfqd, bfqq, "active");
+               bfq_log_bfqq(bfqd, bfqq, "set_active_queue, cur-budget = %lu",
+                            bfqq->entity.budget);
        }
 
        bfqd->active_queue = bfqq;
@@ -509,7 +549,26 @@ static struct bfq_queue *bfq_set_active_
        return bfqq;
 }
 
-#define CIC_SEEKY(cic) ((cic)->seek_mean > (8 * 1024))
+/*
+ * If enough samples have been computed, return the current max budget
+ * stored in bfqd, which is dynamically updated according to the
+ * estimated disk peak rate; otherwise return the default max budget
+ */
+static inline unsigned long bfq_max_budget(struct bfq_data *bfqd)
+{
+       return bfqd->budgets_assigned < 194 ? bfq_default_max_budget :
+               bfqd->bfq_max_budget;
+}
+
+/*
+ * Return min budget, which is a fraction of the current or default
+ * max budget (trying with 1/32)
+ */
+static inline unsigned long bfq_min_budget(struct bfq_data *bfqd)
+{
+       return bfqd->budgets_assigned < 194 ? bfq_default_max_budget / 32 :
+               bfqd->bfq_max_budget / 32;
+}
 
 static void bfq_arm_slice_timer(struct bfq_data *bfqd)
 {
@@ -531,19 +590,30 @@ static void bfq_arm_slice_timer(struct b
        bfq_mark_bfqq_wait_request(bfqq);
 
        /*
-        * we don't want to idle for seeks, but we do want to allow
+        * We don't want to idle for seeks, but we do want to allow
         * fair distribution of slice time for a process doing back-to-back
-        * seeks. so allow a little bit of time for him to submit a new rq
+        * seeks. So allow a little bit of time for him to submit a new rq.
+        *
+        * To prevent processes with (partly) seeky workloads from
+        * being too ill-treated, grant them a small fraction of the
+        * assigned budget before reducing the waiting time to
+        * BFQ_MIN_TT. This happened to help reduce latency.
         */
        sl = bfqd->bfq_slice_idle;
-       if (bfq_sample_valid(cic->seek_samples) && CIC_SEEKY(cic))
+       if (bfq_sample_valid(bfqq->seek_samples) && BFQQ_SEEKY(bfqq) &&
+           bfqq->entity.service > bfq_max_budget(bfqd) / 8)
                sl = min(sl, msecs_to_jiffies(BFQ_MIN_TT));
 
        bfqd->last_idling_start = ktime_get();
        mod_timer(&bfqd->idle_slice_timer, jiffies + sl);
-       bfq_log(bfqd, "arm idle: %lu", sl);
+       bfq_log(bfqd, "arm idle: %lu ms", sl);
 }
 
+/*
+ * Set the maximum time for the active queue to consume its
+ * budget. This prevents seeky processes from lowering the disk
+ * throughput (always guaranteed with a time slice scheme as in CFQ).
+ */
 static void bfq_set_budget_timeout(struct bfq_data *bfqd)
 {
        struct bfq_queue *bfqq = bfqd->active_queue;
@@ -552,7 +622,8 @@ static void bfq_set_budget_timeout(struc
 
        bfq_clear_bfqq_budget_new(bfqq);
        bfqq->budget_timeout = jiffies +
-               bfqd->bfq_timeout[!!bfq_bfqq_sync(bfqq)];
+               bfqd->bfq_timeout[!!bfq_bfqq_sync(bfqq)] *
+               (bfqq->entity.weight / bfqq->entity.orig_weight);
 }
 
 /*
@@ -572,7 +643,7 @@ static void bfq_dispatch_insert(struct r
 }
 
 /*
- * return expired entry, or NULL to just start from scratch in rbtree
+ * Return expired entry, or NULL to just start from scratch in rbtree.
  */
 static struct request *bfq_check_fifo(struct bfq_queue *bfqq)
 {
@@ -597,7 +668,7 @@ static struct request *bfq_check_fifo(st
        return rq;
 }
 
-static inline bfq_service_t bfq_bfqq_budget_left(struct bfq_queue *bfqq)
+static inline unsigned long bfq_bfqq_budget_left(struct bfq_queue *bfqq)
 {
        struct bfq_entity *entity = &bfqq->entity;
        return entity->budget - entity->service;
@@ -616,98 +687,115 @@ static void __bfq_bfqq_expire(struct bfq
 }
 
 /**
- * bfq_default_budget - return the default budget for @bfqq on @bfqd.
- * @bfqd: the device descriptor.
- * @bfqq: the queue to consider.
- *
- * We use 3/4 of the @bfqd maximum budget as the default value
- * for the max_budget field of the queues.  This lets the feedback
- * mechanism to start from some middle ground, then the behavior
- * of the task will drive the heuristics towards high values, if
- * it behaves as a greedy sequential reader, or towards small values
- * if it shows a more intermittent behavior.
- */
-static bfq_service_t bfq_default_budget(struct bfq_data *bfqd,
-                                       struct bfq_queue *bfqq)
-{
-       bfq_service_t budget;
-
-       /*
-        * When we need an estimate of the peak rate we need to avoid
-        * to give budgets that are too short due to previous measurements.
-        * So, in the first 10 assignments use a ``safe'' budget value.
-        */
-       if (bfqq->budgets_assigned < 194 && bfqd->bfq_user_max_budget == 0)
-               budget = bfq_max_budget;
-       else
-               budget = bfqd->bfq_max_budget;
-
-       return budget - budget / 4;
-}
-
-static inline bfq_service_t bfq_min_budget(struct bfq_data *bfqd,
-                                          struct bfq_queue *bfqq)
-{
-       return bfqd->bfq_max_budget / 2;
-}
-
-/**
  * __bfq_bfqq_recalc_budget - try to adapt the budget to the @bfqq behavior.
  * @bfqd: device data.
  * @bfqq: queue to update.
  * @reason: reason for expiration.
  *
- * Handle the feedback on @bfqq budget.  This is driven by the following
- * principles:
- *   - async queues get always the maximum budget value (their ability to
- *     dispatch is limited by @bfqd->bfq_max_budget_async_rq).
- *   - If @bfqq has been too idle we decrease its budget, as it is likely
- *     to be more interested in latency than in throughput.
- *   - If @bfqq took too much to consume its budget it is likely to be
- *     seeky, so reset the budget to the default, in order to have all
- *     the seeky queues to be charged for the same service, trying to
- *     achieve fairness at least in the time domain among them.
- *   - If @bfqq exhausted its budget treat it as a greedy reader, in
- *     order to run it at full speed.
- *   - If @bfqq expired due to lack of requests leave its budget untouched.
+ * Handle the feedback on @bfqq budget.  See the body for detailed
+ * comments.
  */
 static void __bfq_bfqq_recalc_budget(struct bfq_data *bfqd,
                                     struct bfq_queue *bfqq,
                                     enum bfqq_expiration reason)
 {
        struct request *next_rq;
-       bfq_service_t budget, min_budget;
+       unsigned long budget, min_budget;
 
        budget = bfqq->max_budget;
-       min_budget = bfq_min_budget(bfqd, bfqq);
+       min_budget = bfq_min_budget(bfqd);
 
        BUG_ON(bfqq != bfqd->active_queue);
 
+       bfq_log_bfqq(bfqd, bfqq, "recalc_budg: last budg %lu, budg left %lu",
+               bfqq->entity.budget, bfq_bfqq_budget_left(bfqq));
+       bfq_log_bfqq(bfqd, bfqq, "recalc_budg: last max_budg %lu, min budg %lu",
+               budget, bfq_min_budget(bfqd));
+       bfq_log_bfqq(bfqd, bfqq, "recalc_budg: sync %d, seeky %d",
+               bfq_bfqq_sync(bfqq), BFQQ_SEEKY(bfqd->active_queue));
+
        if (bfq_bfqq_sync(bfqq)) {
                switch (reason) {
+               /*
+                * Caveat: in all the following cases we trade latency
+                * for throughput.
+                */
                case BFQ_BFQQ_TOO_IDLE:
-                       if (budget > min_budget + BFQ_BUDGET_STEP)
-                               budget -= BFQ_BUDGET_STEP;
-                       else
-                               budget = min_budget;
+                       /*
+                        * This is the only case where we may reduce
+                        * the budget: if there is no requets of the
+                        * process still waiting for completion, then
+                        * we assume (tentatively) that the timer has
+                        * expired because the batch of requests of
+                        * the process could have been served with a
+                        * smaller budget.  Hence, betting that
+                        * process will behave in the same way when it
+                        * becomes backlogged again, we reduce its
+                        * next budget.  As long as we guess right,
+                        * this budget cut reduces the latency
+                        * experienced by the process.
+                        *
+                        * However, if there are still outstanding
+                        * requests, then the process may have not yet
+                        * issued its next request just because it is
+                        * still waiting for the completion of some of
+                        * the still oustanding ones.  So in this
+                        * subcase we do not reduce its budget, on the
+                        * contrary we increase it to possibly boost
+                        * the throughput, as discussed in the
+                        * comments to the BUDGET_TIMEOUT case.
+                        */
+                       if (bfqq->dispatched > 0) /* still oustanding reqs */
+                               budget = min(budget * 2, bfqd->bfq_max_budget);
+                       else {
+                               if (budget > 5 * min_budget)
+                                       budget -= 4 * min_budget;
+                               else
+                                       budget = min_budget;
+                       }
                        break;
                case BFQ_BFQQ_BUDGET_TIMEOUT:
-                       budget = bfq_default_budget(bfqd, bfqq);
+                       /*
+                        * We double the budget here because: 1) it
+                        * gives the chance to boost the throughput if
+                        * this is not a seeky process (which may have
+                        * bumped into this timeout because of, e.g.,
+                        * ZBR), 2) together with charge_full_budget
+                        * it helps give seeky processes higher
+                        * timestamps, and hence be served less
+                        * frequently.
+                        */
+                       budget = min(budget * 2, bfqd->bfq_max_budget);
                        break;
                case BFQ_BFQQ_BUDGET_EXHAUSTED:
-                       budget = min(budget + 8 * BFQ_BUDGET_STEP,
-                                    bfqd->bfq_max_budget);
+                       /*
+                        * The process still has backlog, and did not
+                        * let either the budget timeout or the disk
+                        * idling timeout expire. Hence it is not
+                        * seeky, has a short thinktime and may be
+                        * happy with a higher budget too. So
+                        * definitely increase the budget of this good
+                        * candidate to boost the disk throughput.
+                        */
+                       budget = min(budget * 4, bfqd->bfq_max_budget);
                        break;
                case BFQ_BFQQ_NO_MORE_REQUESTS:
+                      /*
+                       * Leave the budget unchanged.
+                       */
                default:
                        return;
                }
-       } else
+       } else /* async queue */
+           /* async queues get always the maximum possible budget
+            * (their ability to dispatch is limited by
+            * @bfqd->bfq_max_budget_async_rq).
+            */
                budget = bfqd->bfq_max_budget;
 
        bfqq->max_budget = budget;
 
-       if (bfqq->budgets_assigned >= 194 && bfqd->bfq_user_max_budget == 0 &&
+       if (bfqd->budgets_assigned >= 194 && bfqd->bfq_user_max_budget == 0 &&
            bfqq->max_budget > bfqd->bfq_max_budget)
                bfqq->max_budget = bfqd->bfq_max_budget;
 
@@ -719,30 +807,40 @@ static void __bfq_bfqq_recalc_budget(str
         */
        next_rq = bfqq->next_rq;
        if (next_rq != NULL)
-               bfqq->entity.budget = max(bfqq->max_budget,
-                                         next_rq->hard_nr_sectors);
-       bfq_log_bfqq(bfqd, bfqq, "budget=%lu (%d)", bfqq->entity.budget,
-                    bfq_bfqq_sync(bfqq));
+               bfqq->entity.budget = max_t(unsigned long, bfqq->max_budget,
+                                           bfq_serv_to_charge(next_rq, bfqq));
+       else
+               bfqq->entity.budget = bfqq->max_budget;
+
+       bfq_log_bfqq(bfqd, bfqq, "head sect: %lu, new budget %lu",
+                       next_rq != NULL ? next_rq->hard_nr_sectors : 0,
+                       bfqq->entity.budget);
 }
 
-static bfq_service_t bfq_calc_max_budget(u64 peak_rate, u64 timeout)
+static unsigned long bfq_calc_max_budget(u64 peak_rate, u64 timeout)
 {
-       bfq_service_t max_budget;
+       unsigned long max_budget;
 
        /*
         * The max_budget calculated when autotuning is equal to the
-        * amount of sectors transfered in 0.75 * timeout_sync at the
+        * amount of sectors transfered in timeout_sync at the
         * estimated peak rate.
         */
-       max_budget = (bfq_service_t)(peak_rate * 1000 *
+       max_budget = (unsigned long)(peak_rate * 1000 *
                                     timeout >> BFQ_RATE_SHIFT);
-       max_budget -= max_budget / 4;
 
        return max_budget;
 }
 
+/*
+ * In addition to updating the peak rate, checks whether the process
+ * is "slow", and returns 1 if so. This slow flag is used, in addition
+ * to the budget timeout, to reduce the amount of service provided to
+ * seeky processes, and hence reduce their chances to lower the
+ * throughput. See the code for more details.
+ */
 static int bfq_update_peak_rate(struct bfq_data *bfqd, struct bfq_queue *bfqq,
-                               int compensate)
+                               int compensate, enum bfqq_expiration reason)
 {
        u64 bw, usecs, expected, timeout;
        ktime_t delta;
@@ -775,10 +873,21 @@ static int bfq_update_peak_rate(struct b
         * the peak rate estimation.
         */
        if (usecs > 20000) {
-               if (bw > bfqd->peak_rate) {
-                       bfqd->peak_rate = bw;
+               if (bw > bfqd->peak_rate ||
+                  (!BFQQ_SEEKY(bfqq) &&
+                   reason == BFQ_BFQQ_BUDGET_TIMEOUT)) {
+                       bfq_log(bfqd, "measured bw =%llu", bw);
+                       /*
+                        * To smooth oscillations use a low-pass filter with
+                        * alpha=7/8, i.e.,
+                        * new_rate = (7/8) * old_rate + (1/8) * bw
+                        */
+                       do_div(bw, 8);
+                       bfqd->peak_rate *= 7;
+                       do_div(bfqd->peak_rate, 8);
+                       bfqd->peak_rate += bw;
                        update = 1;
-                       bfq_log(bfqd, "peak_rate=%llu", bw);
+                       bfq_log(bfqd, "new peak_rate=%llu", bfqd->peak_rate);
                }
 
                update |= bfqd->peak_rate_samples == BFQ_PEAK_RATE_SAMPLES - 1;
@@ -790,11 +899,22 @@ static int bfq_update_peak_rate(struct b
                    update && bfqd->bfq_user_max_budget == 0) {
                        bfqd->bfq_max_budget =
                                bfq_calc_max_budget(bfqd->peak_rate, timeout);
-                       bfq_log(bfqd, "max_budget=%lu", bfqd->bfq_max_budget);
+                       bfq_log(bfqd, "new max_budget=%lu",
+                               bfqd->bfq_max_budget);
                }
        }
 
        /*
+        * If the process has been served for a too short time
+        * interval to let its possible sequential accesses prevail on
+        * the initial seek time needed to move the disk head on the
+        * first sector it requested, then give the process a chance
+        * and for the moment return false.
+        */
+       if (bfqq->entity.budget <= bfq_max_budget(bfqd) / 8)
+               return 0;
+
+       /*
         * A process is considered ``slow'' (i.e., seeky, so that we
         * cannot treat it fairly in the service domain, as it would
         * slow down too much the other processes) if, when a slice
@@ -804,26 +924,46 @@ static int bfq_update_peak_rate(struct b
         */
        expected = bw * 1000 * timeout >> BFQ_RATE_SHIFT;
 
-       return expected > bfqq->entity.budget;
+       /*
+        * Caveat: processes doing IO in the slower disk zones will
+        * tend to be slow(er) even if not seeky. And the estimated
+        * peak rate will actually be an average over the disk
+        * surface. Hence, to not be too harsh with unlucky processes,
+        * we keep a budget/3 margin of safety before declaring a
+        * process slow.
+        */
+       return expected > (4 * bfqq->entity.budget) / 3;
 }
 
-/*
+/**
  * bfq_bfqq_expire - expire a queue.
  * @bfqd: device owning the queue.
  * @bfqq: the queue to expire.
  * @compensate: if true, compensate for the time spent idling.
  * @reason: the reason causing the expiration.
  *
- * The behavior is the following: when a queue expires because it has
- * been idling for too much we sync its finish time with the service
- * received and decrease its budget.  If @bfqq expires due to budget
- * exhaustion we increase its budget and sync its finish time.
- * If @bfqq expires due to budget timeout we do not sync its finish time
- * to avoid seeky queues to take too much disk time; instead we charge
- * it the maximum budget value.  Using the max budget value for all the
- * queues that expire due to budget timeout has the effect of using the
- * WF2Q+ scheduler to assign timeslices to those queues, without violating
- * the service domain guarantees for well-behaved queues.
+ *
+ * If the process associated to the queue is slow (i.e., seeky), or in
+ * case of budget timeout, or, finally, if it is async, we
+ * artificially charge it an entire budget (independently of the
+ * actual service it received). As a consequence, the queue will get
+ * higher timestamps than the correct ones upon reactivation, and
+ * hence it will be rescheduled as if it had received more service
+ * than what it actually received. In the end, this class of processes
+ * will receive less service in proportion to how slowly they consume
+ * their budgets (and hence how seriously they tend to lower the
+ * throughput).
+ *
+ * In contrast, when a queue expires because it has been idling for
+ * too much or because it exhausted its budget, we do not touch the
+ * amount of service it has received. Hence when the queue will be
+ * reactivated and its timestamps updated, the latter will be in sync
+ * with the actual service received by the queue until expiration.
+ *
+ * Charging a full budget to the first type of queues and the exact
+ * service to the others has the effect of using the WF2Q+ policy to
+ * schedule the former on a timeslice basis, without violating the
+ * service domain guarantees of the latter.
  */
 static void bfq_bfqq_expire(struct bfq_data *bfqd,
                            struct bfq_queue *bfqq,
@@ -831,27 +971,42 @@ static void bfq_bfqq_expire(struct bfq_d
                            enum bfqq_expiration reason)
 {
        int slow;
+       BUG_ON(bfqq != bfqd->active_queue);
 
-       slow = bfq_update_peak_rate(bfqd, bfqq, compensate);
+       /* Update disk peak rate for autotuning and check whether the
+        * process is slow (see bfq_update_peak_rate).
+        */
+       slow = bfq_update_peak_rate(bfqd, bfqq, compensate, reason);
 
        /*
-        * Treat slow (i.e., seeky) traffic as timed out, to not favor
-        * it over sequential traffic (a seeky queue consumes less budget,
-        * so it would receive smaller timestamps wrt a sequential one
-        * when an idling timer fires).
+        * As above explained, 'punish' slow (i.e., seeky), timed-out
+        * and async queues, to favor sequential sync workloads.
+        *
+        * Processes doing IO in the slower disk zones will tend to be
+        * slow(er) even if not seeky. Hence, since the estimated peak
+        * rate is actually an average over the disk surface, these
+        * processes may timeout just for bad luck. To avoid punishing
+        * them we do not charge a full budget to a process that
+        * succeeded in consuming at least 2/3 of its budget.
         */
-       if (slow && reason == BFQ_BFQQ_TOO_IDLE)
-               reason = BFQ_BFQQ_BUDGET_TIMEOUT;
-
-       if (reason == BFQ_BFQQ_BUDGET_TIMEOUT || !bfq_bfqq_sync(bfqq))
+       if (slow || (reason == BFQ_BFQQ_BUDGET_TIMEOUT &&
+                    bfq_bfqq_budget_left(bfqq) >=  bfqq->entity.budget / 3))
                bfq_bfqq_charge_full_budget(bfqq);
 
-       bfq_log_bfqq(bfqd, bfqq, "expire (%d, %d)", reason, slow);
+       bfq_log_bfqq(bfqd, bfqq,
+               "expire (%d, slow %d, num_disp %d, idle_win %d)", reason, slow,
+               bfqq->dispatched, bfq_bfqq_idle_window(bfqq));
 
+       /* Increase, decrease or leave budget unchanged according to reason */
        __bfq_bfqq_recalc_budget(bfqd, bfqq, reason);
        __bfq_bfqq_expire(bfqd, bfqq);
 }
 
+/*
+ * Budget timeout is not implemented through a dedicated timer, but
+ * just checked on request arrivals and completions, as well as on
+ * idle timer expirations.
+ */
 static int bfq_bfqq_budget_timeout(struct bfq_queue *bfqq)
 {
        if (bfq_bfqq_budget_new(bfqq))
@@ -864,6 +1019,22 @@ static int bfq_bfqq_budget_timeout(struc
 }
 
 /*
+ * If we expire a queue that is waiting for the arrival of a new
+ * request, we may prevent the fictitious timestamp backshifting that
+ * allows the guarantees of the queue to be preserved (see [1] for
+ * this tricky aspect). Hence we return true only if this condition
+ * does not hold, or if the queue is slow enough to deserve only to be
+ * kicked off for preserving a high throughput.
+*/
+static inline int bfq_may_expire_for_budg_timeout(struct bfq_queue *bfqq)
+{
+       return (!bfq_bfqq_wait_request(bfqq) ||
+               bfq_bfqq_budget_left(bfqq) >=  bfqq->entity.budget / 3)
+               &&
+               bfq_bfqq_budget_timeout(bfqq);
+}
+
+/*
  * Select a queue for service.  If we have a current active queue,
  * check whether to continue servicing it, or retrieve and set a new one.
  */
@@ -877,10 +1048,10 @@ static struct bfq_queue *bfq_select_queu
        if (bfqq == NULL)
                goto new_queue;
 
-       if (bfq_bfqq_budget_timeout(bfqq)) {
-               bfq_bfqq_charge_full_budget(bfqq);
+       bfq_log_bfqq(bfqd, bfqq, "select_queue: already active queue");
+
+       if (bfq_may_expire_for_budg_timeout(bfqq))
                goto expire;
-       }
 
        next_rq = bfqq->next_rq;
        /*
@@ -888,7 +1059,8 @@ static struct bfq_queue *bfq_select_queu
         * serve them, keep the queue, otherwise expire it.
         */
        if (next_rq != NULL) {
-               if (next_rq->hard_nr_sectors > bfq_bfqq_budget_left(bfqq)) {
+               if (bfq_serv_to_charge(next_rq, bfqq) >
+                       bfq_bfqq_budget_left(bfqq)) {
                        reason = BFQ_BFQQ_BUDGET_EXHAUSTED;
                        goto expire;
                } else
@@ -896,9 +1068,8 @@ static struct bfq_queue *bfq_select_queu
        }
 
        /*
-        * No requests pending.  If the active queue still has requests in
-        * flight or is idling for a new request, allow either of these
-        * conditions to happen (or time out) before selecting a new queue.
+        * No requests pending.  If the active queue still has
+        * requests in flight or is idling for a new request, then keep it.
         */
        if (timer_pending(&bfqd->idle_slice_timer) ||
            (bfqq->dispatched != 0 && bfq_bfqq_idle_window(bfqq))) {
@@ -911,6 +1082,7 @@ expire:
        bfq_bfqq_expire(bfqd, bfqq, 0, reason);
 new_queue:
        bfqq = bfq_set_active_queue(bfqd);
+       bfq_log(bfqd, "select_queue: new queue returned (possibly NULL)");
 keep_queue:
        return bfqq;
 }
@@ -929,13 +1101,15 @@ static int __bfq_dispatch_requests(struc
 
        do {
                struct request *rq;
+               unsigned long service_to_charge;
 
                /* Follow expired path, else get first next available. */
                rq = bfq_check_fifo(bfqq);
                if (rq == NULL)
                        rq = bfqq->next_rq;
+               service_to_charge = bfq_serv_to_charge(rq, bfqq);
 
-               if (rq->hard_nr_sectors > bfq_bfqq_budget_left(bfqq)) {
+               if (service_to_charge > bfq_bfqq_budget_left(bfqq)) {
                        /*
                         * Expire the queue for budget exhaustion, and
                         * make sure that the next act_budget is enough
@@ -947,9 +1121,41 @@ static int __bfq_dispatch_requests(struc
                }
 
                /* Finally, insert request into driver dispatch list. */
-               bfq_bfqq_served(bfqq, rq->hard_nr_sectors);
+               bfq_bfqq_served(bfqq, service_to_charge);
                bfq_dispatch_insert(bfqd->queue, rq);
 
+               if (bfqq->high_weight_budget > 0) { /* queue is being boosted */
+                       struct bfq_entity *entity = &bfqq->entity;
+
+                       bfq_log_bfqq(bfqd, bfqq, "busy period dur %llu msec, "
+                                    "old highwbudg %lu",
+                                    jiffies_to_msecs(jiffies) -
+                                    bfqq->last_activation_time,
+                                    bfqq->high_weight_budget);
+                       /*
+                        * Decrease the budget for weight boosting by
+                        * the just received service, or, if too much
+                        * time has elapsed from the beginning of this
+                        * boosting period, stop it
+                        */
+                       if (jiffies_to_msecs(jiffies) -
+                           bfqq->last_activation_time <= BFQ_BOOST_TIMEOUT
+                           &&
+                           bfqq->high_weight_budget > service_to_charge)
+                               bfqq->high_weight_budget -= service_to_charge;
+                       else
+                               bfqq->high_weight_budget = 0;
+                       entity->ioprio_changed = 1;
+                       __bfq_entity_update_weight_prio(
+                               bfq_entity_service_tree(entity),
+                               entity);
+               }
+
+               bfq_log_bfqq(bfqd, bfqq, "dispatched %lu sec req (%llu), "
+                               "budg left %lu",
+                               rq->hard_nr_sectors, rq->hard_sector,
+                               bfq_bfqq_budget_left(bfqq));
+
                dispatched++;
 
                if (bfqd->active_cic == NULL) {
@@ -961,6 +1167,8 @@ static int __bfq_dispatch_requests(struc
                        break;
        } while (dispatched < max_dispatch);
 
+       bfq_log_bfqq(bfqd, bfqq, "dispatched %d reqs", dispatched);
+
        if (bfqd->busy_queues > 1 && ((!bfq_bfqq_sync(bfqq) &&
            dispatched >= bfqd->bfq_max_budget_async_rq) ||
            bfq_class_idle(bfqq)))
@@ -1009,7 +1217,7 @@ static int bfq_forced_dispatch(struct bf
                st = bfq_entity_service_tree(&bfqq->entity);
 
                dispatched += __bfq_forced_dispatch_bfqq(bfqq);
-               bfqq->max_budget = bfq_default_budget(bfqd, bfqq);
+               bfqq->max_budget = bfq_max_budget(bfqd);
 
                bfq_forget_idle(st);
        }
@@ -1025,6 +1233,7 @@ static int bfq_dispatch_requests(struct 
        struct bfq_queue *bfqq;
        int dispatched;
 
+       bfq_log(bfqd, "dispatch requests: %d busy queues", bfqd->busy_queues);
        if (bfqd->busy_queues == 0)
                return 0;
 
@@ -1056,9 +1265,11 @@ static int bfq_dispatch_requests(struct 
                BUG_ON(timer_pending(&bfqd->idle_slice_timer));
 
                dispatched += __bfq_dispatch_requests(bfqd, bfqq, max_dispatch);
+               bfq_log_bfqq(bfqd, bfqq, "total dispatched increased to %d "
+                            "(max_disp %d)", dispatched, max_dispatch);
        }
 
-       bfq_log(bfqd, "dispatched=%d", dispatched);
+       bfq_log(bfqd, "final total dispatched=%d", dispatched);
        return dispatched;
 }
 
@@ -1074,6 +1285,7 @@ static void bfq_put_queue(struct bfq_que
 
        BUG_ON(atomic_read(&bfqq->ref) <= 0);
 
+       bfq_log_bfqq(bfqd, bfqq, "put_queue: %p %d", bfqq, bfqq->ref);
        if (!atomic_dec_and_test(&bfqq->ref))
                return;
 
@@ -1083,7 +1295,7 @@ static void bfq_put_queue(struct bfq_que
        BUG_ON(bfq_bfqq_busy(bfqq));
        BUG_ON(bfqd->active_queue == bfqq);
 
-       bfq_log_bfqq(bfqd, bfqq, "freed");
+       bfq_log_bfqq(bfqd, bfqq, "put_queue: %p freed", bfqq);
 
        kmem_cache_free(bfq_pool, bfqq);
 }
@@ -1095,6 +1307,7 @@ static void bfq_exit_bfqq(struct bfq_dat
                bfq_schedule_dispatch(bfqd);
        }
 
+       bfq_log_bfqq(bfqd, bfqq, "exit_bfqq: %p, %d", bfqq, bfqq->ref);
        bfq_put_queue(bfqq);
 }
 
@@ -1116,7 +1329,7 @@ static void bfq_init_prio_data(struct bf
                printk(KERN_ERR "bfq: bad prio %x\n", ioprio_class);
        case IOPRIO_CLASS_NONE:
                /*
-                * no prio set, inherit CPU scheduling settings
+                * No prio set, inherit CPU scheduling settings.
                 */
                bfqq->entity.new_ioprio = task_nice_ioprio(tsk);
                bfqq->entity.new_ioprio_class = task_nice_ioclass(tsk);
@@ -1139,8 +1352,8 @@ static void bfq_init_prio_data(struct bf
        bfqq->entity.ioprio_changed = 1;
 
        /*
-        * keep track of original prio settings in case we have to temporarily
-        * elevate the priority of this queue
+        * Keep track of original prio settings in case we have to temporarily
+        * elevate the priority of this queue.
         */
        bfqq->org_ioprio = bfqq->entity.new_ioprio;
        bfqq->org_ioprio_class = bfqq->entity.new_ioprio_class;
@@ -1167,6 +1380,9 @@ static void bfq_changed_ioprio(struct io
                                         GFP_ATOMIC);
                if (new_bfqq != NULL) {
                        cic->cfqq[ASYNC] = new_bfqq;
+                       bfq_log_bfqq(bfqd, bfqq,
+                                    "changed_ioprio: bfqq %p %d",
+                                    bfqq, bfqq->ref);
                        bfq_put_queue(bfqq);
                }
        }
@@ -1233,9 +1449,13 @@ retry:
                                bfq_mark_bfqq_idle_window(bfqq);
                        bfq_mark_bfqq_sync(bfqq);
                }
-               bfqq->max_budget = bfq_default_budget(bfqd, bfqq);
+               /* Tentative initial value to trade off between thr and lat */
+               bfqq->max_budget = (2 * bfq_max_budget(bfqd)) / 3;
                bfqq->pid = current->pid;
 
+               bfqq->last_activation_time = 0;
+               bfqq->high_weight_budget = 0;
+
                bfq_log_bfqq(bfqd, bfqq, "allocated");
        }
 
@@ -1285,14 +1505,17 @@ static struct bfq_queue *bfq_get_queue(s
        }
 
        /*
-        * pin the queue now that it's allocated, scheduler exit will prune it
+        * Pin the queue now that it's allocated, scheduler exit will prune it.
         */
        if (!is_sync && *async_bfqq == NULL) {
                atomic_inc(&bfqq->ref);
+               bfq_log_bfqq(bfqd, bfqq, "get_queue, bfqq not in async: %p, %d",
+                            bfqq, bfqq->ref);
                *async_bfqq = bfqq;
        }
 
        atomic_inc(&bfqq->ref);
+       bfq_log_bfqq(bfqd, bfqq, "get_queue, at end: %p, %d", bfqq, bfqq->ref);
        return bfqq;
 }
 
@@ -1309,35 +1532,35 @@ static void bfq_update_io_thinktime(stru
 
 static void bfq_update_io_seektime(struct bfq_data *bfqd,
                                   struct bfq_queue *bfqq,
-                                  struct cfq_io_context *cic,
                                   struct request *rq)
 {
        sector_t sdist;
        u64 total;
 
-       if (cic->last_request_pos < rq->sector)
-               sdist = rq->sector - cic->last_request_pos;
+       if (bfqq->last_request_pos < rq->sector)
+               sdist = rq->sector - bfqq->last_request_pos;
        else
-               sdist = cic->last_request_pos - rq->sector;
+               sdist = bfqq->last_request_pos - rq->sector;
 
        /*
         * Don't allow the seek distance to get too large from the
         * odd fragment, pagein, etc.
         */
-       if (cic->seek_samples == 0) /* first request, not really a seek */
+       if (bfqq->seek_samples == 0) /* first request, not really a seek */
                sdist = 0;
-       else if (cic->seek_samples <= 60) /* second&third seek */
-               sdist = min(sdist, (cic->seek_mean * 4) + 2*1024*1024);
+       else if (bfqq->seek_samples <= 60) /* second & third seek */
+               sdist = min(sdist, (bfqq->seek_mean * 4) + 2*1024*1024);
        else
-               sdist = min(sdist, (cic->seek_mean * 4) + 2*1024*64);
+               sdist = min(sdist, (bfqq->seek_mean * 4) + 2*1024*64);
 
-       cic->seek_samples = (7*cic->seek_samples + 256) / 8;
-       cic->seek_total = (7*cic->seek_total + (u64)256*sdist) / 8;
-       total = cic->seek_total + (cic->seek_samples/2);
-       do_div(total, cic->seek_samples);
-       cic->seek_mean = (sector_t)total;
+       bfqq->seek_samples = (7*bfqq->seek_samples + 256) / 8;
+       bfqq->seek_total = (7*bfqq->seek_total + (u64)256*sdist) / 8;
+       total = bfqq->seek_total + (bfqq->seek_samples/2);
+       do_div(total, bfqq->seek_samples);
+       bfqq->seek_mean = (sector_t)total;
 
-       bfq_log_bfqq(bfqd, bfqq, "dist=%lu mean=%lu", sdist, cic->seek_mean);
+       bfq_log_bfqq(bfqd, bfqq, "dist=%llu mean=%llu", (u64)sdist,
+                       (u64)bfqq->seek_mean);
 }
 
 /*
@@ -1357,7 +1580,7 @@ static void bfq_update_idle_window(struc
        enable_idle = bfq_bfqq_idle_window(bfqq);
 
        if (atomic_read(&cic->ioc->nr_tasks) == 0 ||
-           bfqd->bfq_slice_idle == 0 || (bfqd->hw_tag && CIC_SEEKY(cic)))
+           bfqd->bfq_slice_idle == 0 || (bfqd->hw_tag && BFQQ_SEEKY(bfqq)))
                enable_idle = 0;
        else if (bfq_sample_valid(cic->ttime_samples)) {
                if (cic->ttime_mean > bfqd->bfq_slice_idle)
@@ -1365,14 +1588,13 @@ static void bfq_update_idle_window(struc
                else
                        enable_idle = 1;
        }
+       bfq_log_bfqq(bfqd, bfqq, "update_idle_window: enable_idle %d",
+               enable_idle);
 
        if (enable_idle)
                bfq_mark_bfqq_idle_window(bfqq);
        else
                bfq_clear_bfqq_idle_window(bfqq);
-
-       bfq_log_bfqq(bfqd, bfqq, "idle_window=%d (%d)",
-                    enable_idle, CIC_SEEKY(cic));
 }
 
 /*
@@ -1388,20 +1610,37 @@ static void bfq_rq_enqueued(struct bfq_d
                bfqq->meta_pending++;
 
        bfq_update_io_thinktime(bfqd, cic);
-       bfq_update_io_seektime(bfqd, bfqq, cic, rq);
-       bfq_update_idle_window(bfqd, bfqq, cic);
+       bfq_update_io_seektime(bfqd, bfqq, rq);
+       if (bfqq->entity.service > bfq_max_budget(bfqd) / 8 ||
+           !BFQQ_SEEKY(bfqq))
+               bfq_update_idle_window(bfqd, bfqq, cic);
+
+       bfq_log_bfqq(bfqd, bfqq,
+                    "rq_enqueued: idle_window=%d (seeky %d, mean %llu)",
+                    bfq_bfqq_idle_window(bfqq), BFQQ_SEEKY(bfqq),
+                    bfqq->seek_mean);
 
-       cic->last_request_pos = rq->sector + rq->nr_sectors;
+       bfqq->last_request_pos = rq->sector + rq->nr_sectors;
 
-       if (bfqq == bfqd->active_queue && bfq_bfqq_wait_request(bfqq)) {
-               /*
-                * If we are waiting for a request for this queue, let it rip
-                * immediately and flag that we must not expire this queue
-                * just now.
-                */
-               bfq_clear_bfqq_wait_request(bfqq);
-               del_timer(&bfqd->idle_slice_timer);
-               blk_start_queueing(bfqd->queue);
+       if (bfqq == bfqd->active_queue) {
+               if (bfq_bfqq_wait_request(bfqq)) {
+                       /*
+                        * If we are waiting for a request for this queue, let
+                        * it rip immediately and flag that we must not expire
+                        * this queue just now.
+                        */
+                       bfq_clear_bfqq_wait_request(bfqq);
+                       del_timer(&bfqd->idle_slice_timer);
+                       /*
+                        * Here we can safely expire the queue, in
+                        * case of budget timeout, without wasting
+                        * guarantees
+                        */
+                       if (bfq_bfqq_budget_timeout(bfqq))
+                               bfq_bfqq_expire(bfqd, bfqq, 0,
+                                               BFQ_BFQQ_BUDGET_TIMEOUT);
+                       blk_start_queueing(bfqd->queue);
+               }
        }
 }
 
@@ -1410,6 +1649,7 @@ static void bfq_insert_request(struct re
        struct bfq_data *bfqd = q->elevator->elevator_data;
        struct bfq_queue *bfqq = RQ_BFQQ(rq);
 
+       assert_spin_locked(bfqd->queue->queue_lock);
        bfq_init_prio_data(bfqq, RQ_CIC(rq)->ioc);
 
        bfq_add_rq_rb(rq);
@@ -1447,7 +1687,8 @@ static void bfq_completed_request(struct
        struct bfq_data *bfqd = bfqq->bfqd;
        const int sync = rq_is_sync(rq);
 
-       bfq_log_bfqq(bfqd, bfqq, "complete");
+       bfq_log_bfqq(bfqd, bfqq, "completed %lu sects req (%d)",
+                       rq->hard_nr_sectors, sync);
 
        bfq_update_hw_tag(bfqd);
 
@@ -1470,7 +1711,7 @@ static void bfq_completed_request(struct
                if (bfq_bfqq_budget_new(bfqq))
                        bfq_set_budget_timeout(bfqd);
 
-               if (bfq_bfqq_budget_timeout(bfqq))
+               if (bfq_may_expire_for_budg_timeout(bfqq))
                        bfq_bfqq_expire(bfqd, bfqq, 0, BFQ_BFQQ_BUDGET_TIMEOUT);
                else if (sync && bfqd->rq_in_driver == 0 &&
                         RB_EMPTY_ROOT(&bfqq->sort_list))
@@ -1489,7 +1730,7 @@ static void bfq_prio_boost(struct bfq_qu
 {
        if (has_fs_excl()) {
                /*
-                * boost idle prio on transactions that would lock out other
+                * Boost idle prio on transactions that would lock out other
                 * users of the filesystem
                 */
                if (bfq_class_idle(bfqq))
@@ -1498,7 +1739,7 @@ static void bfq_prio_boost(struct bfq_qu
                        bfqq->entity.new_ioprio = IOPRIO_NORM;
        } else {
                /*
-                * check if we need to unboost the queue
+                * Check if we need to unboost the queue
                 */
                if (bfqq->entity.new_ioprio_class != bfqq->org_ioprio_class)
                        bfqq->entity.new_ioprio_class = bfqq->org_ioprio_class;
@@ -1527,7 +1768,7 @@ static int bfq_may_queue(struct request_
        /*
         * Don't force setup of a queue from here, as a call to may_queue
         * does not necessarily imply that a request actually will be queued.
-        * so just lookup a possibly existing queue, or return 'may queue'
+        * So just lookup a possibly existing queue, or return 'may queue'
         * if that fails.
         */
        cic = bfq_cic_lookup(bfqd, tsk->io_context);
@@ -1546,7 +1787,7 @@ static int bfq_may_queue(struct request_
 }
 
 /*
- * queue lock held here
+ * Queue lock held here.
  */
 static void bfq_put_request(struct request *rq)
 {
@@ -1563,6 +1804,8 @@ static void bfq_put_request(struct reque
                rq->elevator_private = NULL;
                rq->elevator_private2 = NULL;
 
+               bfq_log_bfqq(bfqq->bfqd, bfqq, "put_request %p, %d",
+                            bfqq, bfqq->ref);
                bfq_put_queue(bfqq);
        }
 }
@@ -1603,6 +1846,7 @@ static int bfq_set_request(struct reques
 
        bfqq->allocated[rw]++;
        atomic_inc(&bfqq->ref);
+       bfq_log_bfqq(bfqd, bfqq, "set_request: bfqq %p, %d", bfqq, bfqq->ref);
 
        spin_unlock_irqrestore(q->queue_lock, flags);
 
@@ -1634,7 +1878,8 @@ static void bfq_kick_queue(struct work_s
 }
 
 /*
- * Timer running if the active_queue is currently idling inside its time slice
+ * Handler of the expiration of the timer running if the active_queue
+ * is idling inside its time slice.
  */
 static void bfq_idle_slice_timer(unsigned long data)
 {
@@ -1643,8 +1888,6 @@ static void bfq_idle_slice_timer(unsigne
        unsigned long flags;
        enum bfqq_expiration reason;
 
-       bfq_log(bfqd, "slice_timer expired");
-
        spin_lock_irqsave(bfqd->queue->queue_lock, flags);
 
        bfqq = bfqd->active_queue;
@@ -1657,8 +1900,14 @@ static void bfq_idle_slice_timer(unsigne
         * we just expire a queue too early.
         */
        if (bfqq != NULL) {
+               bfq_log_bfqq(bfqd, bfqq, "slice_timer expired");
                reason = BFQ_BFQQ_TOO_IDLE;
                if (bfq_bfqq_budget_timeout(bfqq))
+                       /*
+                        * Also here the queue can be safely expired
+                        * for budget timeout without wasting
+                        * guarantees
+                        */
                        reason = BFQ_BFQQ_BUDGET_TIMEOUT;
 
                bfq_bfqq_expire(bfqd, bfqq, 1, reason);
@@ -1681,8 +1930,11 @@ static inline void __bfq_put_async_bfqq(
        struct bfq_group *root_group = bfqd->root_group;
        struct bfq_queue *bfqq = *bfqq_ptr;
 
+       bfq_log(bfqd, "put_async_bfqq: %p", bfqq);
        if (bfqq != NULL) {
                bfq_bfqq_move(bfqd, bfqq, &bfqq->entity, root_group);
+               bfq_log_bfqq(bfqd, bfqq, "put_async_bfqq: putting %p, %d",
+                            bfqq, bfqq->ref);
                bfq_put_queue(bfqq);
                *bfqq_ptr = NULL;
        }
@@ -1705,7 +1957,7 @@ static void bfq_put_async_queues(struct 
        __bfq_put_async_bfqq(bfqd, &bfqg->async_idle_bfqq);
 }
 
-static void bfq_exit_queue(elevator_t *e)
+static void bfq_exit_queue(struct elevator_queue *e)
 {
        struct bfq_data *bfqd = e->elevator_data;
        struct request_queue *q = bfqd->queue;
@@ -1772,7 +2024,7 @@ static void *bfq_init_queue(struct reque
 
        bfqd->hw_tag = 1;
 
-       bfqd->bfq_max_budget = bfq_max_budget;
+       bfqd->bfq_max_budget = bfq_default_max_budget;
 
        bfqd->bfq_quantum = bfq_quantum;
        bfqd->bfq_fifo_expire[0] = bfq_fifo_expire[0];
@@ -1784,6 +2036,8 @@ static void *bfq_init_queue(struct reque
        bfqd->bfq_timeout[ASYNC] = bfq_timeout_async;
        bfqd->bfq_timeout[SYNC] = bfq_timeout_sync;
 
+       bfqd->low_latency = true;
+
        return bfqd;
 }
 
@@ -1819,16 +2073,19 @@ static ssize_t bfq_var_show(unsigned int
        return sprintf(page, "%d\n", var);
 }
 
-static ssize_t bfq_var_store(unsigned int *var, const char *page, size_t count)
+static ssize_t bfq_var_store(unsigned long *var, const char *page, size_t count)
 {
-       char *p = (char *)page;
+       unsigned long new_val;
+       int ret = strict_strtoul(page, 10, &new_val);
+
+       if (ret == 0)
+               *var = new_val;
 
-       *var = simple_strtoul(p, &p, 10);
        return count;
 }
 
 #define SHOW_FUNCTION(__FUNC, __VAR, __CONV)                           \
-static ssize_t __FUNC(elevator_t *e, char *page)                       \
+static ssize_t __FUNC(struct elevator_queue *e, char *page)            \
 {                                                                      \
        struct bfq_data *bfqd = e->elevator_data;                       \
        unsigned int __data = __VAR;                                    \
@@ -1846,13 +2103,15 @@ SHOW_FUNCTION(bfq_max_budget_show, bfqd-
 SHOW_FUNCTION(bfq_max_budget_async_rq_show, bfqd->bfq_max_budget_async_rq, 0);
 SHOW_FUNCTION(bfq_timeout_sync_show, bfqd->bfq_timeout[SYNC], 1);
 SHOW_FUNCTION(bfq_timeout_async_show, bfqd->bfq_timeout[ASYNC], 1);
+SHOW_FUNCTION(bfq_low_latency_show, bfqd->low_latency, 0);
 #undef SHOW_FUNCTION
 
 #define STORE_FUNCTION(__FUNC, __PTR, MIN, MAX, __CONV)                        \
-static ssize_t __FUNC(elevator_t *e, const char *page, size_t count)   \
+static ssize_t                                                         \
+__FUNC(struct elevator_queue *e, const char *page, size_t count)       \
 {                                                                      \
        struct bfq_data *bfqd = e->elevator_data;                       \
-       unsigned int __data;                                            \
+       unsigned long __data;                                           \
        int ret = bfq_var_store(&__data, (page), count);                \
        if (__data < (MIN))                                             \
                __data = (MIN);                                         \
@@ -1879,21 +2138,21 @@ STORE_FUNCTION(bfq_timeout_async_store, 
                INT_MAX, 1);
 #undef STORE_FUNCTION
 
-static inline bfq_service_t bfq_estimated_max_budget(struct bfq_data *bfqd)
+static inline unsigned long bfq_estimated_max_budget(struct bfq_data *bfqd)
 {
        u64 timeout = jiffies_to_msecs(bfqd->bfq_timeout[SYNC]);
 
        if (bfqd->peak_rate_samples >= BFQ_PEAK_RATE_SAMPLES)
                return bfq_calc_max_budget(bfqd->peak_rate, timeout);
        else
-               return bfq_max_budget;
+               return bfq_default_max_budget;
 }
 
-static ssize_t bfq_max_budget_store(elevator_t *e, const char *page,
-                                   size_t count)
+static ssize_t bfq_max_budget_store(struct elevator_queue *e,
+                                   const char *page, size_t count)
 {
        struct bfq_data *bfqd = e->elevator_data;
-       unsigned int __data;
+       unsigned long __data;
        int ret = bfq_var_store(&__data, (page), count);
 
        if (__data == 0)
@@ -1909,11 +2168,11 @@ static ssize_t bfq_max_budget_store(elev
        return ret;
 }
 
-static ssize_t bfq_timeout_sync_store(elevator_t *e, const char *page,
-                                     size_t count)
+static ssize_t bfq_timeout_sync_store(struct elevator_queue *e,
+                                     const char *page, size_t count)
 {
        struct bfq_data *bfqd = e->elevator_data;
-       unsigned int __data;
+       unsigned long __data;
        int ret = bfq_var_store(&__data, (page), count);
 
        if (__data < 1)
@@ -1928,6 +2187,20 @@ static ssize_t bfq_timeout_sync_store(el
        return ret;
 }
 
+static ssize_t bfq_low_latency_store(struct elevator_queue *e,
+                                    const char *page, size_t count)
+{
+       struct bfq_data *bfqd = e->elevator_data;
+       unsigned long __data;
+       int ret = bfq_var_store(&__data, (page), count);
+
+       if (__data > 1)
+               __data = 1;
+       bfqd->low_latency = __data;
+
+       return ret;
+}
+
 #define BFQ_ATTR(name) \
        __ATTR(name, S_IRUGO|S_IWUSR, bfq_##name##_show, bfq_##name##_store)
 
@@ -1942,12 +2215,13 @@ static struct elv_fs_entry bfq_attrs[] =
        BFQ_ATTR(max_budget_async_rq),
        BFQ_ATTR(timeout_sync),
        BFQ_ATTR(timeout_async),
+       BFQ_ATTR(low_latency),
        __ATTR_NULL
 };
 
 static struct elevator_type iosched_bfq = {
        .ops = {
-               .elevator_merge_fn =            bfq_merge,
+               .elevator_merge_fn =            bfq_merge,
                .elevator_merged_fn =           bfq_merged_request,
                .elevator_merge_req_fn =        bfq_merged_requests,
                .elevator_allow_merge_fn =      bfq_allow_merge,
@@ -1974,7 +2248,7 @@ static struct elevator_type iosched_bfq 
 static int __init bfq_init(void)
 {
        /*
-        * can be 0 on HZ < 1000 setups
+        * Can be 0 on HZ < 1000 setups.
         */
        if (bfq_slice_idle == 0)
                bfq_slice_idle = 1;
diff -uprN linux-2.6.28/block/bfq-sched.c linux-2.6.28.new/block/bfq-sched.c
--- linux-2.6.28/block/bfq-sched.c      2011-06-13 21:41:23.766107399 +0200
+++ linux-2.6.28.new/block/bfq-sched.c  2011-06-13 21:41:41.639927001 +0200
@@ -28,7 +28,7 @@ static int bfq_update_next_active(struct
                return 0;
 
        /*
-        * NOTE: this can be improved in may ways, such as returning
+        * NOTE: this can be improved in many ways, such as returning
         * 1 (and thus propagating upwards the update) only when the
         * budget changes, or caching the bfqq that will be scheduled
         * next from this subtree.  By now we worry more about
@@ -85,20 +85,33 @@ static inline void bfq_check_next_active
  *
  * Return @a > @b, dealing with wrapping correctly.
  */
-static inline int bfq_gt(bfq_timestamp_t a, bfq_timestamp_t b)
+static inline int bfq_gt(u64 a, u64 b)
 {
        return (s64)(a - b) > 0;
 }
 
+static inline struct bfq_queue *bfq_entity_to_bfqq(struct bfq_entity *entity)
+{
+       struct bfq_queue *bfqq = NULL;
+
+       BUG_ON(entity == NULL);
+
+       if (entity->my_sched_data == NULL)
+               bfqq = container_of(entity, struct bfq_queue, entity);
+
+       return bfqq;
+}
+
+
 /**
  * bfq_delta - map service into the virtual time domain.
  * @service: amount of service.
- * @weight: scale factor.
+ * @weight: scale factor (weight of an entity or weight sum).
  */
-static inline bfq_timestamp_t bfq_delta(bfq_service_t service,
-                                       bfq_weight_t weight)
+static inline u64 bfq_delta(unsigned long service,
+                                       unsigned long weight)
 {
-       bfq_timestamp_t d = (bfq_timestamp_t)service << WFQ_SERVICE_SHIFT;
+       u64 d = (u64)service << WFQ_SERVICE_SHIFT;
 
        do_div(d, weight);
        return d;
@@ -110,11 +123,25 @@ static inline bfq_timestamp_t bfq_delta(
  * @service: the service to be charged to the entity.
  */
 static inline void bfq_calc_finish(struct bfq_entity *entity,
-                                  bfq_service_t service)
+                                  unsigned long service)
 {
+       struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
+
        BUG_ON(entity->weight == 0);
 
-       entity->finish = entity->start + bfq_delta(service, entity->weight);
+       entity->finish = entity->start +
+               bfq_delta(service, entity->weight);
+
+       if (bfqq != NULL) {
+               bfq_log_bfqq(bfqq->bfqd, bfqq,
+                       "calc_finish: serv %lu, w %lu, hi-budg %lu",
+                       service, entity->weight,
+                       bfqq->high_weight_budget);
+               bfq_log_bfqq(bfqq->bfqd, bfqq,
+                       "calc_finish: start %llu, finish %llu, delta %llu",
+                       entity->start, entity->finish,
+                       bfq_delta(service, entity->weight));
+       }
 }
 
 /**
@@ -150,18 +177,6 @@ static inline void bfq_extract(struct rb
        rb_erase(&entity->rb_node, root);
 }
 
-static inline struct bfq_queue *bfq_entity_to_bfqq(struct bfq_entity *entity)
-{
-       struct bfq_queue *bfqq = NULL;
-
-       BUG_ON(entity == NULL);
-
-       if (entity->my_sched_data == NULL)
-               bfqq = container_of(entity, struct bfq_queue, entity);
-
-       return bfqq;
-}
-
 /**
  * bfq_idle_extract - extract an entity from the idle tree.
  * @st: the service tree of the owning @entity.
@@ -325,12 +340,26 @@ static void bfq_active_insert(struct bfq
  * bfq_ioprio_to_weight - calc a weight from an ioprio.
  * @ioprio: the ioprio value to convert.
  */
-static bfq_weight_t bfq_ioprio_to_weight(int ioprio)
+static unsigned short bfq_ioprio_to_weight(int ioprio)
 {
        WARN_ON(ioprio < 0 || ioprio >= IOPRIO_BE_NR);
        return IOPRIO_BE_NR - ioprio;
 }
 
+/**
+ * bfq_weight_to_ioprio - calc an ioprio from a weight.
+ * @weight: the weight value to convert.
+ *
+ * To preserve as mush as possible the old only-ioprio user interface,
+ * 0 is used as an escape ioprio value for weights (numerically) equal or
+ * larger than IOPRIO_BE_NR
+ */
+static unsigned short bfq_weight_to_ioprio(int weight)
+{
+       WARN_ON(weight < BFQ_MIN_WEIGHT || weight > BFQ_MAX_WEIGHT);
+       return IOPRIO_BE_NR - weight < 0 ? 0 : IOPRIO_BE_NR - weight;
+}
+
 static inline void bfq_get_entity(struct bfq_entity *entity)
 {
        struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
@@ -339,6 +368,8 @@ static inline void bfq_get_entity(struct
        if (bfqq != NULL) {
                sd = entity->sched_data;
                atomic_inc(&bfqq->ref);
+               bfq_log_bfqq(bfqq->bfqd, bfqq, "get_entity: %p %d",
+                            bfqq, bfqq->ref);
        }
 }
 
@@ -437,6 +468,8 @@ static void bfq_forget_entity(struct bfq
        st->wsum -= entity->weight;
        if (bfqq != NULL) {
                sd = entity->sched_data;
+               bfq_log_bfqq(bfqq->bfqd, bfqq, "forget_entity: %p %d",
+                            bfqq, bfqq->ref);
                bfq_put_queue(bfqq);
        }
 }
@@ -478,6 +511,62 @@ static void bfq_forget_idle(struct bfq_s
                bfq_put_idle_entity(st, first_idle);
 }
 
+static struct bfq_service_tree *
+__bfq_entity_update_weight_prio(struct bfq_service_tree *old_st,
+                        struct bfq_entity *entity)
+{
+       struct bfq_service_tree *new_st = old_st;
+
+       if (entity->ioprio_changed) {
+               int new_boost_coeff = 1;
+               struct bfq_queue *bfqq = bfq_entity_to_bfqq(entity);
+
+               if (bfqq != NULL) {
+                       new_boost_coeff +=
+                               bfqq->high_weight_budget * BFQ_BOOST_COEFF /
+                               BFQ_BOOST_BUDGET;
+                       bfq_log_bfqq(bfqq->bfqd, bfqq,
+                               "update_w_prio: wght %lu, hi-budg %lu, coef %d",
+                               entity->weight, bfqq->high_weight_budget,
+                               new_boost_coeff);
+               }
+
+               BUG_ON(old_st->wsum < entity->weight);
+               old_st->wsum -= entity->weight;
+
+               if (entity->new_weight != entity->orig_weight) {
+                       entity->orig_weight = entity->new_weight;
+                       entity->ioprio =
+                               bfq_weight_to_ioprio(entity->orig_weight);
+               } else if (entity->new_ioprio != entity->ioprio) {
+                       entity->ioprio = entity->new_ioprio;
+                       entity->orig_weight =
+                                       bfq_ioprio_to_weight(entity->ioprio);
+               } else
+                       entity->new_weight = entity->orig_weight =
+                               bfq_ioprio_to_weight(entity->ioprio);
+
+               entity->ioprio_class = entity->new_ioprio_class;
+               entity->ioprio_changed = 0;
+
+               /*
+                * NOTE: here we may be changing the weight too early,
+                * this will cause unfairness.  The correct approach
+                * would have required additional complexity to defer
+                * weight changes to the proper time instants (i.e.,
+                * when entity->finish <= old_st->vtime).
+                */
+               new_st = bfq_entity_service_tree(entity);
+               entity->weight = entity->orig_weight * new_boost_coeff;
+               new_st->wsum += entity->weight;
+
+               if (new_st != old_st)
+                       entity->start = new_st->vtime;
+       }
+
+       return new_st;
+}
+
 /**
  * bfq_bfqq_served - update the scheduler status after selection for service.
  * @bfqq: the queue being served.
@@ -487,7 +576,7 @@ static void bfq_forget_idle(struct bfq_s
  * are synchronized every time a new bfqq is selected for service.  By now,
  * we keep it to better check consistency.
  */
-static void bfq_bfqq_served(struct bfq_queue *bfqq, bfq_service_t served)
+static void bfq_bfqq_served(struct bfq_queue *bfqq, unsigned long served)
 {
        struct bfq_entity *entity = &bfqq->entity;
        struct bfq_service_tree *st;
@@ -496,13 +585,13 @@ static void bfq_bfqq_served(struct bfq_q
                st = bfq_entity_service_tree(entity);
 
                entity->service += served;
-
                WARN_ON_ONCE(entity->service > entity->budget);
                BUG_ON(st->wsum == 0);
 
                st->vtime += bfq_delta(served, st->wsum);
                bfq_forget_idle(st);
        }
+       bfq_log_bfqq(bfqq->bfqd, bfqq, "bfqq_served %lu secs", served);
 }
 
 /**
@@ -515,42 +604,13 @@ static void bfq_bfqq_served(struct bfq_q
  * budget.  In this way we should obtain a sort of time-domain
  * fairness among all the seeky/slow queues.
  */
-static void bfq_bfqq_charge_full_budget(struct bfq_queue *bfqq)
+static inline void bfq_bfqq_charge_full_budget(struct bfq_queue *bfqq)
 {
        struct bfq_entity *entity = &bfqq->entity;
 
-       bfq_bfqq_served(bfqq, entity->budget - entity->service);
-}
+       bfq_log_bfqq(bfqq->bfqd, bfqq, "charge_full_budget");
 
-static struct bfq_service_tree *
-__bfq_entity_update_prio(struct bfq_service_tree *old_st,
-                        struct bfq_entity *entity)
-{
-       struct bfq_service_tree *new_st = old_st;
-
-       if (entity->ioprio_changed) {
-               entity->ioprio = entity->new_ioprio;
-               entity->ioprio_class = entity->new_ioprio_class;
-               entity->ioprio_changed = 0;
-
-               old_st->wsum -= entity->weight;
-               entity->weight = bfq_ioprio_to_weight(entity->ioprio);
-
-               /*
-                * NOTE: here we may be changing the weight too early,
-                * this will cause unfairness.  The correct approach
-                * would have required additional complexity to defer
-                * weight changes to the proper time instants (i.e.,
-                * when entity->finish <= old_st->vtime).
-                */
-               new_st = bfq_entity_service_tree(entity);
-               new_st->wsum += entity->weight;
-
-               if (new_st != old_st)
-                       entity->start = new_st->vtime;
-       }
-
-       return new_st;
+       bfq_bfqq_served(bfqq, entity->budget - entity->service);
 }
 
 /**
@@ -607,7 +667,7 @@ static void __bfq_activate_entity(struct
                entity->on_st = 1;
        }
 
-       st = __bfq_entity_update_prio(st, entity);
+       st = __bfq_entity_update_weight_prio(st, entity);
        bfq_calc_finish(entity, entity->budget);
        bfq_active_insert(st, entity);
 }
diff -uprN linux-2.6.28/block/bfq.h linux-2.6.28.new/block/bfq.h
--- linux-2.6.28/block/bfq.h    2011-06-13 21:41:23.766107399 +0200
+++ linux-2.6.28.new/block/bfq.h        2011-06-13 21:41:41.639927001 +0200
@@ -1,5 +1,5 @@
 /*
- * BFQ: data structures and common functions prototypes.
+ * BFQ-v1-r1 for 2.6.35: data structures and common functions prototypes.
  *
  * Based on ideas and code from CFQ:
  * Copyright (C) 2003 Jens Axboe <axboe@kernel.dk>
@@ -21,12 +21,22 @@
 
 #define BFQ_IOPRIO_CLASSES     3
 
-#define BFQ_DEFAULT_GRP_IOPRIO 4
+#define BFQ_MIN_WEIGHT 1
+#define BFQ_MAX_WEIGHT 1000
+
+#define BFQ_DEFAULT_GRP_WEIGHT 10
+#define BFQ_DEFAULT_GRP_IOPRIO 0
 #define BFQ_DEFAULT_GRP_CLASS  IOPRIO_CLASS_BE
 
-typedef u64 bfq_timestamp_t;
-typedef unsigned long bfq_weight_t;
-typedef unsigned long bfq_service_t;
+/* Constants used in weight boosting (in its turn used to reduce latencies): */
+/* max factor by which the weight of a boosted queue is multiplied */
+#define BFQ_BOOST_COEFF        10
+/* max number of sectors that can be served during a boosting period */
+#define BFQ_BOOST_BUDGET       49152
+/* max duration of a boosting period, msec */
+#define BFQ_BOOST_TIMEOUT      6000
+/* min idle period after which boosting may be reactivated for a queue, msec */
+#define BFQ_MIN_ACT_INTERVAL   20000
 
 struct bfq_entity;
 
@@ -51,8 +61,8 @@ struct bfq_service_tree {
        struct bfq_entity *first_idle;
        struct bfq_entity *last_idle;
 
-       bfq_timestamp_t vtime;
-       bfq_weight_t wsum;
+       u64 vtime;
+       unsigned long wsum;
 };
 
 /**
@@ -92,17 +102,19 @@ struct bfq_sched_data {
  *             this entity; used for O(log N) lookups into active trees.
  * @service: service received during the last round of service.
  * @budget: budget used to calculate F_i; F_i = S_i + @budget / @weight.
- * @weight: weight of the queue, calculated as IOPRIO_BE_NR - @ioprio.
+ * @weight: weight of the queue
  * @parent: parent entity, for hierarchical scheduling.
  * @my_sched_data: for non-leaf nodes in the cgroup hierarchy, the
  *                 associated scheduler queue, %NULL on leaf nodes.
  * @sched_data: the scheduler queue this entity belongs to.
  * @ioprio: the ioprio in use.
- * @new_ioprio: when an ioprio change is requested, the new ioprio value
+ * @new_weight: when a weight change is requested, the new weight value.
+ * @orig_weight: original weight, used to implement weight boosting
+ * @new_ioprio: when an ioprio change is requested, the new ioprio value.
  * @ioprio_class: the ioprio_class in use.
  * @new_ioprio_class: when an ioprio_class change is requested, the new
  *                    ioprio_class value.
- * @ioprio_changed: flag, true when the user requested an ioprio or
+ * @ioprio_changed: flag, true when the user requested a weight, ioprio or
  *                  ioprio_class change.
  *
  * A bfq_entity is used to represent either a bfq_queue (leaf node in the
@@ -111,36 +123,39 @@ struct bfq_sched_data {
  * hierarchy.  Non-leaf entities have also their own sched_data, stored
  * in @my_sched_data.
  *
- * Each entity stores independently its priority values; this would allow
- * different weights on different devices, but this functionality is not
- * exported to userspace by now.  Priorities are updated lazily, first
- * storing the new values into the new_* fields, then setting the
- * @ioprio_changed flag.  As soon as there is a transition in the entity
- * state that allows the priority update to take place the effective and
- * the requested priority values are synchronized.
- *
- * The weight value is calculated from the ioprio to export the same
- * interface as CFQ.  When dealing with ``well-behaved'' queues (i.e.,
- * queues that do not spend too much time to consume their budget and
- * have true sequential behavior, and when there are no external factors
- * breaking anticipation) the relative weights at each level of the
- * cgroups hierarchy should be guaranteed.
- * All the fields are protected by the queue lock of the containing bfqd.
+ * Each entity stores independently its priority values; this would
+ * allow different weights on different devices, but this
+ * functionality is not exported to userspace by now.  Priorities and
+ * weights are updated lazily, first storing the new values into the
+ * new_* fields, then setting the @ioprio_changed flag.  As soon as
+ * there is a transition in the entity state that allows the priority
+ * update to take place the effective and the requested priority
+ * values are synchronized.
+ *
+ * Unless cgroups are used, the weight value is calculated from the
+ * ioprio to export the same interface as CFQ.  When dealing with
+ * ``well-behaved'' queues (i.e., queues that do not spend too much
+ * time to consume their budget and have true sequential behavior, and
+ * when there are no external factors breaking anticipation) the
+ * relative weights at each level of the cgroups hierarchy should be
+ * guaranteed.  All the fields are protected by the queue lock of the
+ * containing bfqd.
  */
 struct bfq_entity {
        struct rb_node rb_node;
 
        int on_st;
 
-       bfq_timestamp_t finish;
-       bfq_timestamp_t start;
+       u64 finish;
+       u64 start;
 
        struct rb_root *tree;
 
-       bfq_timestamp_t min_start;
+       u64 min_start;
 
-       bfq_service_t service, budget;
-       bfq_weight_t weight;
+       unsigned long service, budget;
+       unsigned short weight, new_weight;
+       unsigned short orig_weight;
 
        struct bfq_entity *parent;
 
@@ -168,6 +183,7 @@ struct bfq_group;
  *                   completed requests .
  * @hw_tag_samples: nr of samples used to calculate hw_tag.
  * @hw_tag: flag set to one if the driver is showing a queueing behavior.
+ * @budgets_assigned: number of budgets assigned.
  * @idle_slice_timer: timer set when idling for the next sequential request
  *                    from the queue under service.
  * @unplug_work: delayed work to restart dispatching on the request queue.
@@ -216,6 +232,8 @@ struct bfq_data {
        int hw_tag_samples;
        int hw_tag;
 
+       int budgets_assigned;
+
        struct timer_list idle_slice_timer;
        struct work_struct unplug_work;
 
@@ -228,7 +246,7 @@ struct bfq_data {
        ktime_t last_idling_start;
        int peak_rate_samples;
        u64 peak_rate;
-       bfq_service_t bfq_max_budget;
+       unsigned long bfq_max_budget;
 
        struct list_head cic_list;
        struct hlist_head group_list;
@@ -244,6 +262,8 @@ struct bfq_data {
        unsigned int bfq_user_max_budget;
        unsigned int bfq_max_budget_async_rq;
        unsigned int bfq_timeout[2];
+
+       bool low_latency;
 };
 
 /**
@@ -260,12 +280,17 @@ struct bfq_data {
  * @max_budget: maximum budget allowed from the feedback mechanism.
  * @budget_timeout: budget expiration (in jiffies).
  * @dispatched: number of requests on the dispatch list or inside driver.
- * @budgets_assigned: number of budgets assigned.
  * @org_ioprio: saved ioprio during boosted periods.
  * @org_ioprio_class: saved ioprio_class during boosted periods.
  * @flags: status flags.
  * @bfqq_list: node for active/idle bfqq list inside our bfqd.
+ * @seek_samples: number of seeks sampled
+ * @seek_total: sum of the distances of the seeks sampled
+ * @seek_mean: mean seek distance
+ * @last_request_pos: position of the last request enqueued
  * @pid: pid of the process owning the queue, used for logging purposes.
+ * @last_activation_time: time of the last (idle -> backlogged) transition
+ * @high_weight_budget: number of sectors left to serve with boosted weight
  *
  * A bfq_queue is a leaf request queue; it can be associated to an io_context
  * or more (if it is an async one).  @cgroup holds a reference to the
@@ -287,11 +312,10 @@ struct bfq_queue {
 
        struct bfq_entity entity;
 
-       bfq_service_t max_budget;
+       unsigned long max_budget;
        unsigned long budget_timeout;
 
        int dispatched;
-       int budgets_assigned;
 
        unsigned short org_ioprio;
        unsigned short org_ioprio_class;
@@ -300,7 +324,15 @@ struct bfq_queue {
 
        struct list_head bfqq_list;
 
+       unsigned int seek_samples;
+       u64 seek_total;
+       sector_t seek_mean;
+       sector_t last_request_pos;
+
        pid_t pid;
+
+       u64 last_activation_time;
+       unsigned long high_weight_budget;
 };
 
 enum bfqq_state_flags {
@@ -400,6 +432,7 @@ struct bfq_group {
 /**
  * struct bfqio_cgroup - bfq cgroup data structure.
  * @css: subsystem state for bfq in the containing cgroup.
+ * @weight: cgroup weight.
  * @ioprio: cgroup ioprio.
  * @ioprio_class: cgroup ioprio_class.
  * @lock: spinlock that protects @ioprio, @ioprio_class and @group_data.
@@ -411,7 +444,7 @@ struct bfq_group {
 struct bfqio_cgroup {
        struct cgroup_subsys_state css;
 
-       unsigned short ioprio, ioprio_class;
+       unsigned short weight, ioprio, ioprio_class;
 
        spinlock_t lock;
        struct hlist_head group_data;