block: prepare I/O context code for BFQ-v6 for 3.1

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>
block: cgroups, kconfig, build bits for BFQ-v6-3.1

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

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
block: introduce the BFQ-v6 I/O sched for 3.1

Add the BFQ-v6 I/O scheduler to 3.1.
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 made a queue is selected and 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.

    - Also with flash-based devices, a high throughput is achieved while
      still preserving latency guarantees.

    - A useful feature borrowed from CFQ: static fallback queue for OOM.

    - Differently from CFQ, BFQ uses a unified mechanism (Early Queue Merge,
      EQM) to get a sequential read pattern, and hence a high throughput,
      with any set of processes performing interleaved I/O. EQM also
      preserves low latency. The code for detecting whether two queues have
      to be merged is a slightly modified version of the CFQ code for
      detecting whether two queues belong to cooperating processes and whether
      the service of a queue should be preempted to boost the throughput.

    - BFQ supports full hierarchical scheduling, exporting a cgroups
      interface.  Each node has a full scheduler, so each group can
      be assigned its own ioprio (mapped to a weight, see next point)
      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 weight 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>
defconfig: enable BFQ I/O scheduler

Change-Id: I8045a968b6878808d5b6dce602e52b9930a1bb66
defconfig: enable CFQ and Deadline I/O schedulers

Change-Id: I4432e339749fb924ac359e025b842939a4390650
block: add SIO I/O scheduler

Change-Id: I6a10dd1c71864b96e8f95a695aecd5107453f687
defconfig: enable SIO I/O scheduler

Change-Id: I93e56a422379a74e0d9e82ec81f51771ecfbc740
block: Adding ROW scheduling algorithm

This patch adds the implementation of a new scheduling algorithm - ROW.
The policy of this algorithm is to prioritize READ requests over WRITE
as much as possible without starving the WRITE requests.
The requests are kept in queues according to their priority. The
dispatch
is done in a Round Robin manner with a different slice for each queue.
READ request queues get bigger dispatch quantum than the write requests.

Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

block: Add support for reinsert a dispatched req

Add support for reinserting a dispatched request back to the
scheduler's internal data structures.
This capability is used by the device driver when it chooses to
interrupt the current request transmission and execute another (more
urgent) pending request. For example: interrupting long write in order
to handle pending read. The device driver re-inserts the
remaining write request back to the scheduler, to be rescheduled
for transmission later on.

Add API for verifying whether the current scheduler
supports reinserting requests mechanism. If reinsert mechanism isn't
supported by the scheduler, this code path will never be activated.

Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

block: Add API for urgent request handling

This patch add support in block & elevator layers for handling
urgent requests. The decision if a request is urgent or not is taken
by the scheduler. Urgent request notification is passed to the
underlying
block device driver (eMMC for example). Block device driver may decide
to
interrupt the currently running low priority request to serve the new
urgent request. By doing so READ latency is greatly reduced in
read&write
collision scenarios.

Note that if the current scheduler doesn't implement the urgent request
mechanism, this code path is never activated.

Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

block: compile ROW statically into the kernel

ROW is a new scheduling algorithm. Similar to the existing scheduling
algorithms it should be compiled to the kernel statically giving the
user
the ability to switch to it without kernel recompilation.

Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

row: Adding support for reinsert already dispatched req

Add support for reinserting already dispatched request back to the
schedulers internal data structures.
The request will be reinserted back to the queue (head) it was
dispatched from as if it was never dispatched.

Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

row: Add support for urgent request handling

This patch add support for handling urgent requests.
ROW queue can be marked as "urgent". If an urgent queue was
un-served in a previous dispatch cycle and a request was added
to it - it will trigger issuing urgent request to the device driver.

Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

block: row: Add some debug information on ROW queues

1. Add a counter for number of requests on queue.
2. Add function to print queues status (number requests
   currently on queue and number of already dispatched requests
   in current dispatch cycle).

Change-Id: I1e98b9ca33853e6e6a8ddc53240f6cd6981e6024
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

block: row: Insert dispatch_quantum into struct row_queue

There is really no point in keeping the dispatch quantum
of a queue outside of it. By inserting it to the row_queue
structure we spare extra level in accessing it.

Change-Id: Ic77571818b643e71f9aafbb2ca93d0a92158b199
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

block: row: fix sysfs functions - idle_time conversion

idle_time was updated to be stored in msec instead of jiffies.
So there is no need to convert the value when reading from user or
displaying the value to him.

Change-Id: I58e074b204e90a90536d32199ac668112966e9cf
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>

block: row: Aggregate row_queue parameters to one structure

Each ROW queues has several parameters which default values are defined
in separate arrays. This patch aggregates all default values into one
array.
The values in question are:
 - is idling enabled for the queue
 - queue quantum
 - can the queue notify on urgent request

Change-Id: I3821b0a042542295069b340406a16b1000873ec6
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
defconfig: enable ROW I/O scheduler

Change-Id: Ia711f104df5215a0ca285b60e07de9efc5d7f5dc
Remove unneeded file

Change-Id: Ibaca820ba566c82b29a07c225a06619852a2f7b0