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.

Change-Id: I4ed52ea21d43b0e7c0769b2599779a3d3869c519
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
block: ROW: Correct minimum values of ROW tunable parameters

The ROW scheduling algorithm exposes several tunable parameters.
This patch updates the minimum allowed values for those parameters.

Change-Id: I5ec19d54b694e2e83ad5376bd99cc91f084967f5
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
block: ROW: Fix forced dispatch

This patch fixes forced dispatch in the ROW scheduling algorithm.
When the dispatch function is called with the forced flag on, we
can't delay the dispatch of the requests that are in scheduler queues.
Thus, when dispatch is called with forced turned on, we need to cancel
idling, or not to idle at all.

Change-Id: I3aa0da33ad7b59c0731c696f1392b48525b52ddc
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.

Change-Id: I70954df300774409c25b5821465fb3aa33d8feb5
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
block:row: fix idling mechanism in ROW

This patch addresses the following issues found in the ROW idling
mechanism:
1. Fix the delay passed to queue_delayed_work (pass actual delay
   and not the time when to start the work)
2. Change the idle time and the idling-trigger frequency to be
   HZ dependent (instead of using msec_to_jiffies())
3. Destroy idle_workqueue() in queue_exit

Change-Id: If86513ad6b4be44fb7a860f29bd2127197d8d5bf
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
row: Add support for urgent request handling

This patch adds support for handling urgent requests.
ROW queue can be marked as "urgent" so if it was un-served in last
dispatch cycle and a request was added to it - it will trigger
issuing an urgent-request-notification to the block device driver.
The block device driver may choose at stop the transmission of current
ongoing request to handle the urgent one. Foe example: long WRITE may
be stopped to handle an urgent READ. This decreases READ latency.

Change-Id: I84954c13f5e3b1b5caeadc9fe1f9aa21208cb35e
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>
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>
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>
block: Kernel changes for ROW scheduler

Scheduler was backported from 3.4 kernel, so these needs to
be changed to match 3.0 kernel.
Update defconfigs for ROW scheduler

Change-Id: Iaafc28c7806e08ed6c1c0b3d287668b6ef0266c9
audio_acdb: avoid NULL pointer dereference
logger: reclaim some ram
cpufreq: Add a boostpulse interface to ondemand
For applications that require a one-shot increase in frequency,
the boostpulse interface would help to scale to max for the time
specified in boostime. This helps applications that currently
increases scaling_min_freq and resets later after a fixed duration.
Instead of changing scaling_min_freq applications can directly write
to boostpulse and governer resets during regular timer after the time
expires.

Change-Id: Ie5f490ff06b41364aa76dd468573433495da28a4
Signed-off-by: Narayanan Gopalakrishnan <nargop@codeaurora.org>
lib/sha1: use the git implementation of SHA-1

For ChromiumOS, we use SHA-1 to verify the integrity of the root
filesystem.  The speed of the kernel sha-1 implementation has a major
impact on our boot performance.

To improve boot performance, we investigated using the heavily optimized
sha-1 implementation used in git.  With the git sha-1 implementation, we
see a 11.7% improvement in boot time.

10 reboots, remove slowest/fastest.

Before:

  Mean: 6.58 seconds Stdev: 0.14

After (with git sha-1, this patch):

  Mean: 5.89 seconds Stdev: 0.07

The other cool thing about the git SHA-1 implementation is that it only
needs 64 bytes of stack for the workspace while the original kernel
implementation needed 320 bytes.

Signed-off-by: Mandeep Singh Baines <msb@chromium.org>
Cc: Ramsay Jones <ramsay@ramsay1.demon.co.uk>
Cc: Nicolas Pitre <nico@cam.org>
Cc: Herbert Xu <herbert@gondor.apana.org.au>
Cc: David S. Miller <davem@davemloft.net>
Cc: linux-crypto@vger.kernel.org
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: nobodyAtall <tsogkas@ceid.upatras.gr>
arm: remove "optimized" SHA1 routines

Since commit 1eb19a12bd22 ("lib/sha1: use the git implementation of
SHA-1"), the ARM SHA1 routines no longer work.  The reason? They
depended on the larger 320-byte workspace, and now the sha1 workspace is
just 16 words (64 bytes).  So the assembly version would overwrite the
stack randomly.

The optimized asm version is also probably slower than the new improved
C version, so there's no reason to keep it around.  At least that was
the case in git, where what appears to be the same assembly language
version was removed two years ago because the optimized C BLK_SHA1 code
was faster.

Reported-and-tested-by: Joachim Eastwood <manabian@gmail.com>
Cc: Andreas Schwab <schwab@linux-m68k.org>
Cc: Nicolas Pitre <nico@fluxnic.net>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: nobodyAtall <tsogkas@ceid.upatras.gr>
arm: remove stale export of 'sha_transform'

The generic library code already exports the generic function, this was
left-over from the ARM-specific version that just got removed.

Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
Signed-off-by: nobodyAtall <tsogkas@ceid.upatras.gr>