Add BFQ-v5r1 I/O Scheduler

Squashed commit of the following:

commit 3210ad349e15826b8ccbc5ce6bdf7878b78bc137
Author: fuzz <fuzzzzzzzzzzzzzzzzzz@gmail.com>
Date:   Sun Jan 27 11:44:29 2013 +0900

    configs: Add BFQ-v5r1 I/O Scheduler

commit 1572aefabef91eb97d1d83c8ece135e8faf79ee4
Author: Arianna Avanzini <avanzini.arianna@gmail.com>
Date:   Mon Sep 12 22:43:15 2011 +0200

    block: introduce the BFQ-v5r1 I/O sched for 3.0

    Add the BFQ-v5r1 I/O scheduler to 3.0.
    The general structure is borrowed from CFQ, as much code. A (bfq_)queue is
    associated to each task doing I/O on a device, and each time a scheduling
    decision has to be taken a queue is selected and it is served until it expires.

        - Slices are given in the service domain: tasks are assigned budgets,
          measured in number of sectors. Once got the disk, a task must
          however consume its assigned budget within a configurable maximum time
          (by default, the maximum possible value of the budgets is automatically
          computed to comply with this timeout). This allows the desired latency
          vs "throughput boosting" tradeoff to be set.

        - Budgets are scheduled according to a variant of WF2Q+, implemented
          using an augmented rb-tree to take eligibility into account while
          preserving an O(log N) overall complexity.

        - A low-latency tunable is provided; if enabled, both interactive and soft
          real-time applications are guaranteed very low latency.

        - Latency guarantees are preserved also in presence of NCQ.

        - High throughput with flash-based devices, while still preserving
          latency guarantees.

        - Useful features borrowed from CFQ: cooperating-queues merging (with
          some additional optimizations with respect to the original CFQ version),
          static fallback queue for OOM.

        - BFQ supports full hierarchical scheduling, exporting a cgroups
          interface.  Each node has a full scheduler, so each group can
          be assigned its own ioprio and an ioprio_class.

        - If the cgroups interface is used, weights can be explictly assigned,
          otherwise ioprio values are mapped to weights using the relation
          weight = IOPRIO_BE_NR - ioprio.

        - ioprio classes are served in strict priority order, i.e., lower
          priority queues are not served as long as there are higher priority
          queues.  Among queues in the same class the bandwidth is distributed
          in proportion to the weights of each queue. A very thin extra bandwidth
          is however guaranteed to the Idle class, to prevent it from starving.

    Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
    Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>

commit 4210f1f8f490645e41fe521f01cd0b3ff0380777
Author: Arianna Avanzini <avanzini.arianna@gmail.com>
Date:   Mon Sep 12 22:42:07 2011 +0200

    block: cgroups, kconfig, build bits for BFQ-v5r1-3.0

    Add a Kconfig option and do the related Makefile changes to compile
    the BFQ I/O scheduler.  Also let the cgroups subsystem know about the
    BFQ I/O controller.

    Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
    Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>

commit 4301ccb8fbfaef0dc68da8a890ce18eda8e7803e
Author: Arianna Avanzini <avanzini.arianna@gmail.com>
Date:   Mon Sep 12 22:40:31 2011 +0200

    block: prepare I/O context code for BFQ-v5r1 for 3.0

    BFQ uses struct cfq_io_context to store its per-process per-device data,
    reusing the same code for cic handling of CFQ.  The code is not shared
    ATM to minimize the impact of these patches.

    This patch introduces a new hlist to each io_context to store all the
    cic's allocated by BFQ to allow calling the right destructor on module
    unload; the radix tree used for cic lookup needs to be duplicated
    because it can contain dead keys inserted by a scheduler and later
    retrieved by the other one.

    Update the io_context exit and free paths to take care also of
    the BFQ cic's.

    Change the type of cfqq inside struct cfq_io_context to void *
    to use it also for BFQ per-queue data.

    A new bfq-specific ioprio_changed field is necessary, too, to avoid
    clobbering cfq's one, so switch ioprio_changed to a bitmap, with one
    element per scheduler.

    Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
    Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>

Change-Id: I95f51f1df6a54fb6f84a637e6e4e21003d84fb8c
Merge remote-tracking branch 'cm/cm-10.1' into cm-10.1