Add ROW I/O Scheduler by Qualcomm.

Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
block: row: squash commits from codeaurora.

Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
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>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
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>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
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>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
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>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
block: row: Dispatch requests according to their io-priority

This patch implements "application-hints" which is a way the issuing
application can notify the scheduler on the priority of its request.
This is done by setting the io-priority of the request.
This patch reuses an already existing mechanism of io-priorities developed
for CFQ. Please refer to kernel/Documentation/block/ioprio.txt for
usage example and explanations.

Change-Id: I228ec8e52161b424242bb7bb133418dc8b73925a
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
block: row: Idling mechanism re-factoring

At the moment idling in ROW is implemented by delayed work that uses
jiffies granularity which is not very accurate. This patch replaces
current idling mechanism implementation with hrtime API, which gives
nanosecond resolution (instead of jiffies).

Change-Id: I86c7b1776d035e1d81571894b300228c8b8f2d92
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
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.

Change-Id: I5c982a66b651ebf544aae60063ac8a340d79e67f
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
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.

Change-Id: I8aa74b9b45c0d3a2221bd4e82ea76eb4103e7cfa
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
block: row: Don't notify URGENT if there are un-completed urgent req

When ROW scheduler reports to the block layer that there is an urgent
request pending, the device driver may decide to stop the transmission
of the current request in order to handle the urgent one. If the current
transmitted request is an urgent request - we don't want it to be
stopped.
Due to the above ROW scheduler won't notify of an urgent request if
there are urgent requests in flight.

Change-Id: I2fa186d911b908ec7611682b378b9cdc48637ac7
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
block: row: Update initial values of ROW data structures

This patch sets the initial values of internal ROW
parameters.

Change-Id: I38132062a7fcbe2e58b9cc757e55caac64d013dc
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>
Revert "block: row: Update initial values of ROW data structures"

This reverts commit 0edd930bf1dd91131c036658d21cc421ddf87399.
Revert "block: row: Don't notify URGENT if there are un-completed urgent req"

This reverts commit 055f349743c534b17bdb67dcfd384f24b8ed809a.
Squash ROW upstream commits

block,elevator: use new hashtable implementation

Switch elevator to use the new hashtable implementation. This reduces the
amount of generic unrelated code in the elevator.

This also removes the dymanic allocation of the hash table. The size of the table is
constant so there's no point in paying the price of an extra dereference when accessing
it.

This patch depends on d9b482c ("hashtable: introduce a small and naive
hashtable") which was merged in v3.6.

Signed-off-by: Sasha Levin <sasha.levin@oracle.com>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>

block: row: Don't notify URGENT if there are un-completed urgent req

When ROW scheduler reports to the block layer that there is an urgent
request pending, the device driver may decide to stop the transmission
of the current request in order to handle the urgent one. If the current
transmitted request is an urgent request - we don't want it to be
stopped.
Due to the above ROW scheduler won't notify of an urgent request if
there are urgent requests in flight.

Change-Id: I2fa186d911b908ec7611682b378b9cdc48637ac7
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>

block: row: Update initial values of ROW data structures

This patch sets the initial values of internal ROW
parameters.

Change-Id: I38132062a7fcbe2e58b9cc757e55caac64d013dc
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
[smuckle@codeaurora.org: ported from msm-3.7]
Signed-off-by: Steve Muckle <smuckle@codeaurora.org>

Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>

block: row: Re-design urgent request notification mechanism

This patch updates the ROW URGENT notification policy to apply with the
bellow:
- Don't notify URGENT if there is an un-completed URGENT request in driver
- After notifying that URGENT request is present, the next request
  dispatched is the URGENT one.
- At every given moment only 1 request can be marked as URGENT.
  Independent of it's location (driver or scheduler)

Other changes to URGENT policy:
- Only queues that are allowed to notify of an URGENT request pending
are READ queues

Change-Id: I17ff73125bc7a760cea1116b466115a2df635a14
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>

block/partitions: optimize memory allocation in check_partition()

Currently, sizeof(struct parsed_partitions) may be 64KB in 32bit arch, so
it is easy to trigger page allocation failure by check_partition,
especially in hotplug block device situation(such as, USB mass storage,
MMC card, ...), and Felipe Balbi has observed the failure.

This patch does below optimizations on the allocation of struct
parsed_partitions to try to address the issue:

- make parsed_partitions.parts as pointer so that the pointed memory can
  fit in 32KB buffer, then approximate 32KB memory can be saved

- vmalloc the buffer pointed by parsed_partitions.parts because 32KB is
  still a bit big for kmalloc

- given that many devices have the partition count limit, so only
  allocate disk_max_parts() partitions instead of 256 partitions always

Signed-off-by: Ming Lei <ming.lei@canonical.com>
Reported-by: Felipe Balbi <balbi@ti.com>
Cc: Jens Axboe <axboe@kernel.dk>
Reviewed-by: Yasuaki Ishimatsu <isimatu.yasuaki@jp.fujitsu.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>

Revert "block: row: Re-design urgent request notification mechanism"

The revert fixes frequent boot up failures on 8974.

This reverts commit 0c3b048d1fae87db150e9ff729a9608e5346e042.

Change-Id: I181513382a128724ce08980ad2f14cd5943c27bd
Signed-off-by: Shashank Babu Chinta Venkata <sbchin@codeaurora.org>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>

block: row: Re-design urgent request notification mechanism

When ROW scheduler reports to the block layer that there is an urgent
request pending, the device driver may decide to stop the transmission
of the current request in order to handle the urgent one. This is done
in order to reduce the latency of an urgent request. For example:
long WRITE may be stopped to handle an urgent READ.

This patch updates the ROW URGENT notification policy to apply with the
below:

- Don't notify URGENT if there is an un-completed URGENT request in driver
- After notifying that URGENT request is present, the next request
  dispatched is the URGENT one.
- At every given moment only 1 request can be marked as URGENT.
  Independent of it's location (driver or scheduler)

Other changes to URGENT policy:
- Only READ queues are allowed to notify of an URGENT request pending.

CR fix:
If a pending urgent request (A) gets merged with another request (B)
A is removed from scheduler queue but is not removed from
rd->pending_urgent_rq.

CRs-Fixed: 453712
Change-Id: I321e8cf58e12a05b82edd2a03f52fcce7bc9a900
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>

block: blk-merge: don't merge the pages with non-contiguous descriptors

blk_rq_map_sg() function merges the physically contiguous pages to use same
scatter-gather node without checking if their page descriptors are
contiguous or not.

Now when dma_map_sg() is called on the scatter gather list, it would
take the base page pointer from each node (one by one) and iterates
through all of the pages in same sg node by keep incrementing the base
page pointer with the assumption that physically contiguous pages will
have their page descriptor address contiguous which may not be true
if SPARSEMEM config is enabled. So here we may end referring to invalid
page descriptor.

Following table shows the example of physically contiguous pages but
their page descriptor addresses non-contiguous.
-------------------------------------------
| Page Descriptor    |   Physical Address |
------------------------------------------
| 0xc1e43fdc         |   0xdffff000       |
| 0xc2052000         |   0xe0000000       |
-------------------------------------------

With this patch, relevant blk-merge functions will also check if the
physically contiguous pages are having page descriptors address contiguous
or not? If not then, these pages are separated to be in different
scatter-gather nodes.

CRs-Fixed: 392141
Change-Id: I3601565e5569a69f06fb3af99061c4d4c23af241
Signed-off-by: Subhash Jadavani <subhashj@codeaurora.org>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>

block: urgent request: remove unnecessary urgent marking

An urgent request is marked by the scheduler in rq->cmd_flags with the
REQ_URGENT flag. There is no need to add an additional marking by
the block layer.

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

Conflicts:
	block/test-iosched.c

block: blk-core: add printk_ratelimit

On failure of requests the console is flooded with prints,
which result in a watchdog bark.
This patch limits the number of prints to console thus, avoiding
the bark.

CRs-Fixed: 458071
Change-Id: I614002cc1305ab7b5c6a64d278139291c1baa3c4
Signed-off-by: Asutosh Das <asutoshd@codeaurora.org>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>

block: urgent request: Update dispatch_urgent in case of requeue/reinsert

The block layer implements a mechanism for verifying that the device
driver won't be notified of an URGENT request if there is already an
URGENT request in flight. This is due to the fact that interrupting an
URGENT request isn't efficient.
This patch fixes the above described mechanism in case the URGENT request
was returned back to the block layer from some reason: by requeue or
reinsert.

CRs-fixed: 473376, 473036, 471736
Change-Id: Ie8b8208230a302d4526068531616984825f1050d
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>

block: row: Prevent starvation of regular priority by high priority

At the moment all REGULAR and LOW priority requests are starved as long as
there are HIGH priority requests to dispatch.
This patch prevents the above starvation by setting a starvation limit the
REGULAR\LOW priority requests can tolerate.

Change-Id: Ibe24207982c2c55d75c0b0230f67e013d1106017
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
Signed-off-by: Francisco Franco <franciscofranco.1990@gmail.com>

hashtable: introduce a small and naive hashtable

This hashtable implementation is using hlist buckets to provide a simple
hashtable to prevent it from getting reimplemented all over the kernel.

Signed-off-by: Sasha Levin <levinsasha928@gmail.com>
[ Merging this now, so that subsystems can start applying Sasha's
  patches that use this   - Linus ]
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>

block: add REQ_URGENT to request flags

This patch adds a new flag to be used in cmd_flags field of struct request
for marking request as urgent.
Urgent request is the one that should be given priority currently handled
(regular) request by the device driver. The decision of a request urgency
is taken by the scheduler.

Change-Id: Ic20470987ef23410f1d0324f96f00578f7df8717
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
Signed-off-by: franciscofranco <franciscofranco.1990@gmail.com>