lib/lzo: Rename lzo1x_decompress.c to lzo1x_decompress_safe.c

Rename the source file to match the function name and thereby
also make room for a possible future even slightly faster
"non-safe" decompressor version.

Signed-off-by: Markus F.X.J. Oberhumer <markus@oberhumer.com>
lib/lzo: Update LZO compression to current upstream version

This commit updates the kernel LZO code to the current upsteam version
which features a significant speed improvement - benchmarking the Calgary
and Silesia test corpora typically shows a doubled performance in
both compression and decompression on modern i386/x86_64/powerpc machines.

Signed-off-by: Markus F.X.J. Oberhumer <markus@oberhumer.com>
lzo: check for length overrun in variable length encoding.

This fix ensures that we never meet an integer overflow while adding
255 while parsing a variable length encoding. It works differently from
commit 206a81c ("lzo: properly check for overruns") because instead of
ensuring that we don't overrun the input, which is tricky to guarantee
due to many assumptions in the code, it simply checks that the cumulated
number of 255 read cannot overflow by bounding this number.

The MAX_255_COUNT is the maximum number of times we can add 255 to a base
count without overflowing an integer. The multiply will overflow when
multiplying 255 by more than MAXINT/255. The sum will overflow earlier
depending on the base count. Since the base count is taken from a u8
and a few bits, it is safe to assume that it will always be lower than
or equal to 2*255, thus we can always prevent any overflow by accepting
two less 255 steps.

This patch also reduces the CPU overhead and actually increases performance
by 1.1% compared to the initial code, while the previous fix costs 3.1%
(measured on x86_64).

The fix needs to be backported to all currently supported stable kernels.

Reported-by: Willem Pinckaers <willem@lekkertech.net>
Cc: "Don A. Bailey" <donb@securitymouse.com>
Cc: stable <stable@vger.kernel.org>
Signed-off-by: Willy Tarreau <w@1wt.eu>
Signed-off-by: Greg Kroah-Hartman <gregkh@linuxfoundation.org>
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>
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>
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>
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>
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>
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: 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>
block: row: Update sysfs functions

All ROW (time related) configurable parameters are stored in ms so there
is no need to convert from/to ms when reading/updating them via sysfs.

Change-Id: Ib6a1de54140b5d25696743da944c076dd6fc02ae
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
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>
block: row: Fix starvation tolerance values

The current starvation tolerance values increase the boot time
since high priority SW requests are delayed by regular priority requests.
In order to overcome this, increase the starvation tolerance values.

Change-Id: I9947fca9927cbd39a1d41d4bd87069df679d3103
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
Signed-off-by: Maya Erez <merez@codeaurora.org>
block: urgent: Fix dispatching of URGENT mechanism

There are cases when blk_peek_request is called not from blk_fetch_request
thus the URGENT request may be started but the flag q->dispatched_urgent is
not updated.

Change-Id: I4fb588823f1b2949160cbd3907f4729767932e12
CRs-fixed: 471736
CRs-fixed: 473036
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
block: Remove "requeuing urgent req" error messages

It is possible for URGENT request to be requeued/reinserted if it was
fetched during the creation of a packed list. This end case is rare and is
not handled at the moment.
This patch changes the messages notifying of the above to debug level
(instead of error) in order to clear the dmesg log.

Change-Id: Ie8bc067e61559a6f702077b95c5dbcc426404232
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
block: row-iosched idling triggered by readahead pages

In the current implementation idling is triggered only by request
insertion frequency. This heuristic is not very accurate and may hit
random requests that shouldn't trigger idling. This patch uses the
PG_readahead flag in struct page's flags, which indicates that the page
is part of a readahead window, to start idling upon dispatch of a request
associated with a readahead page.

The above readehead flag is used together with the existing
insertion-frequency trigger. The frequency timer will catch read requests
which are not part of a readahead window, but are still part of a
sequential stream (and therefore dispatched in small time intervals).

Change-Id: Icb7145199c007408de3f267645ccb842e051fd00
Signed-off-by: Lee Susman <lsusman@codeaurora.org>
block: row: change hrtimer_cancel to hrtimer_try_to_cancel

Calling hrtimer_cancel with interrupts disabled can result in a livelock.
When flushing plug list in the block layer interrupts are disabled and an
hrtimer is used when adding requests from that plug list to the scheduler.
In this code flow, if the hrtimer (which is used for idling) is set, it's
being canceled by calling hrtimer_cancel. hrtimer_cancel will perform
the following in an endless loop:
1. try cancel the timer
2. if fails - rest_cpu
the cancellation can fail if the timer function already started. Since
interrupts are disabled it can never complete.
This patch reduced the number of times the hrtimer lock is taken while
interrupts are disabled by calling hrtimer_try_co_cancel. the later will
try to cancel the timer just once and return with an error code if fails.

CRs-fixed: 499887
Change-Id: I25f79c357426d72ad67c261ce7cb503ae97dc7b9
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
block: row: Remove warning massage from add_request

Regular priority queues is marked as "starved" if it skipped a dispatch
due to being empty. When a new request is added to a "starved" queue
it will be marked as urgent.
The removed WARN_ON was warning about an impossible case when a regular
priority (read) queue was marked as starved but wasn't empty. This is
a possible case due to the bellow:
If the device driver fetched a read request that is pending for
transmission and an URGENT request arrives, the fetched read will be
reinserted back to the scheduler. Its possible that the queue it will be
reinserted to was marked as "starved" in the meanwhile due to being empty.

CRs-fixed: 517800
Change-Id: Iaae642ea0ed9c817c41745b0e8ae2217cc684f0c
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
block: do not notify urgent request, when flush with data in flight

MMC device driver implements URGENT request execution with priority
(using stop flow), as a result currently running (and prepared) request
may be reinserted back into I/O scheduler. This will break block layer
logic of flushes (flush request should not be inserted into I/O scheduler).

Block layer flush machinery keep q->flush_data_in_flight list updated with
started but not completed flush requests with data (REQ_FUA).

This change will not notify underling block device driver about pending
urgent request during flushes in flight.

Change-Id: I8b654925a3c989250fcb8f4f7c998795fb203923
Signed-off-by: Konstantin Dorfman <kdorfman@codeaurora.org>
Signed-off-by: Tatyana Brokhman <tlinder@codeaurora.org>
block: row: Fix crash when adding a new field in bio struct

When adding new field to struct bio there is a crash in the removed
code lines. This issue was introduced by commit
80a8f0f87bee18283e9ca0a8966ec97ad9f084e5 "block: row-iosched idling
triggered by readahead pages"

(Partly) reverting this patch till root cause is fixed (on FS level).

Change-Id: Ie82bc806ea52a6370b57aa15455c85b2db10d0da
Signed-off-by: Tanya Brokhman <tlinder@codeaurora.org>