mm: pass readahead info down to the i/o scheduler

Some i/o schedulers (i.e. row-iosched, cfq-iosched) deploy an idling
algorithm in order to be better synced with the readahead algorithm.
Idling is a prediction algorithm for incoming read requests.

In this patch we mark pages which are part of a readahead window, by
setting a newly introduced flag. With this flag, the i/o scheduler can
identify a request which is associated with a readahead page. This
enables the i/o scheduler's idling mechanism to be en-sync with the
readahead mechanism and, in turn, can increase read throughput.

Change-Id: I0654f23315b6d19d71bcc9cc029c6b281a44b196
Signed-off-by: Lee Susman <lsusman@codeaurora.org>
block: Adding ROW scheduling algorithm *merged*

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: 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: 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: 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: Adding ROW scheduling algorithm

(This is a combination of 21 commits.)

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: 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: 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: 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: 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>
cfq-iosched: Fix null pointer dereference

NULL pointer dereference can happen in cfq_choose_cfqg()
when there are no cfq groups to select other than the
current serving group. Prevent this by adding a NULL
check before dereferencing.

Unable to handle kernel NULL pointer dereference at virtual address
[<c02502cc>] (cfq_dispatch_requests+0x368/0x8c0) from
[<c0243f30>] (blk_peek_request+0x220/0x25c)
[<c0243f30>] (blk_peek_request+0x220/0x25c) from
[<c0243f74>] (blk_fetch_request+0x8/0x1c)
[<c0243f74>] (blk_fetch_request+0x8/0x1c) from
[<c041cedc>] (mmc_queue_thread+0x58/0x120)
[<c041cedc>] (mmc_queue_thread+0x58/0x120) from
[<c00ad310>] (kthread+0x84/0x90)
[<c00ad310>] (kthread+0x84/0x90) from
[<c000eeac>] (kernel_thread_exit+0x0/0x8)

CRs-Fixed: 416466
Change-Id: I1fab93a4334b53e1d7c5dcc8f93cff174bae0d5e
Signed-off-by: Sujit Reddy Thumma <sthumma@codeaurora.org>
block: test-iosched: *merge* CAF/LNX.LA.3.5.3_RB2.5
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>
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>
block: add runtime pm
block: add runtime pm helpers

Add runtime pm helper functions:

void blk_pm_runtime_init(struct request_queue *q, struct device *dev)
  - Initialization function for drivers to call.

int blk_pre_runtime_suspend(struct request_queue *q)
  - If any requests are in the queue, mark last busy and return -EBUSY.
    Otherwise set q->rpm_status to RPM_SUSPENDING and return 0.

void blk_post_runtime_suspend(struct request_queue *q, int err)
  - If the suspend succeeded then set q->rpm_status to RPM_SUSPENDED.
    Otherwise set it to RPM_ACTIVE and mark last busy.

void blk_pre_runtime_resume(struct request_queue *q)
  - Set q->rpm_status to RPM_RESUMING.

void blk_post_runtime_resume(struct request_queue *q, int err)
  - If the resume succeeded then set q->rpm_status to RPM_ACTIVE
    and call __blk_run_queue, then mark last busy and autosuspend.
    Otherwise set q->rpm_status to RPM_SUSPENDED.

The idea and API is designed by Alan Stern and described here:
http://marc.info/?l=linux-scsi&m=133727953625963&w=2

Change-Id: I486612af79c7887116f70a4fde552c107f7fa360
Signed-off-by: Lin Ming <ming.m.lin@intel.com>
Signed-off-by: Aaron Lu <aaron.lu@intel.com>
Acked-by: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
Git-commit: 6c9546675864f51506af69eca388e5d922942c56
Git-repo: git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Signed-off-by: Sujit Reddy Thumma <sthumma@codeaurora.org>

block: implement runtime pm strategy

When a request is added:
    If device is suspended or is suspending and the request is not a
    PM request, resume the device.

When the last request finishes:
    Call pm_runtime_mark_last_busy().

When pick a request:
    If device is resuming/suspending, then only PM request is allowed
    to go.

The idea and API is designed by Alan Stern and described here:
http://marc.info/?l=linux-scsi&m=133727953625963&w=2

Change-Id: If9c8332164afba6aeca984277e3398008ad9c45a
Signed-off-by: Lin Ming <ming.m.lin@intel.com>
Signed-off-by: Aaron Lu <aaron.lu@intel.com>
Acked-by: Alan Stern <stern@rowland.harvard.edu>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
Git-commit: c8158819d506a8aedeca53c52dfb709a0aabe011
Git-repo: git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Signed-off-by: Sujit Reddy Thumma <sthumma@codeaurora.org>

blkpm: avoid sleep when holding queue lock

In blk_post_runtime_resume, an autosuspend request will be initiated for
the device. Since we are holding the queue lock, we can't sleep and thus
we should use the async version to initiate an autosuspend, i.e.
pm_request_suspend instead of pm_runtime_suspend, which might sleep.

Change-Id: I28cbe7e20ffdcb8f7b3329bf3b827c942dd1b45a
Signed-off-by: Aaron Lu <aaron.lu@intel.com>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
Git-commit: c60855cdb976c632b3bf8922eeab8a0e78edfc04
Git-repo: git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
Signed-off-by: Sujit Reddy Thumma <sthumma@codeaurora.org>
block: deadline: Allow 0ms deadline latency, increase the read speed

Change a timer compare from after to after-equals, thus allowing
0 timeout and making deadline schedule FIFO.

Signed-off-by: xiaobing tu <xiaobing.tu@intel.com>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
block: Convert kmalloc_node(...GFP_ZERO...) to kzalloc_node(...)

Use the helper function instead of __GFP_ZERO.

Signed-off-by: Joe Perches <joe@perches.com>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
block CFQ: avoid moving request to different queue

request is queued in cfqq->fifo list. Looks it's possible we are moving a
request from one cfqq to another in request merge case. In such case, adjusting
the fifo list order doesn't make sense and is impossible if we don't iterate
the whole fifo list.

My test does hit one case the two cfqq are different, but didn't cause kernel
crash, maybe it's because fifo list isn't used frequently. Anyway, from the
code logic, this is buggy.

I thought we can re-enable the recusive merge logic after this is fixed.

Signed-off-by: Shaohua Li <shli@fusionio.com>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
block: recursive merge requests

In a workload, thread 1 accesses a, a+2, ..., thread 2 accesses a+1, a+3,....
When the requests are flushed to queue, a and a+1 are merged to (a, a+1), a+2
and a+3 too to (a+2, a+3), but (a, a+1) and (a+2, a+3) aren't merged.

If we do recursive merge for such interleave access, some workloads throughput
get improvement. A recent worload I'm checking on is swap, below change
boostes the throughput around 5% ~ 10%.

Signed-off-by: Shaohua Li <shli@fusionio.com>
Signed-off-by: Jens Axboe <axboe@kernel.dk>
lib: *merging updates from* CAF/LNX.LA.3.5.3_RB2.5

uuid: use prandom_bytes()

Use prandom_bytes() to generate 16 bytes of pseudo-random bytes.

Signed-off-by: Akinobu Mita <akinobu.mita@gmail.com>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Huang Ying <ying.huang@intel.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

genalloc: Correct nbytes calculation on long boundary

In existing code we calculate nbytes based on the byte
boundary, but genalloc uses bitmap for maintaining the
memory allocation aligned to long. So while calculating
nbytes we end up getting wrong nbytes.
example: lets say nbytes comes to 9 bytes for 70 bits when
bytes aligned,but if long aligned we will have 3 long words
i.e 12 bytes. This difference may lead to choosing the
wrong api for freeing the memory i.e Between kfree() and
vfree().
Fix was inspired by an upstream commit
eedce141cd2dad8d0cefc5468ef41898949a7031, bringing same fix
into the gen_pool_detroy path.

Change-Id: I942caf59e25515c780896b328b912604df9e10bf
Signed-off-by: Hareesh Gundu <hareeshg@codeaurora.org>
Signed-off-by: Sunil Khatri <sunilkh@codeaurora.org>

lib/scatterlist: error handling in __sg_alloc_table()

I was reviewing code which I suspected might allocate a zero size SG
table.  That will cause memory corruption.  Also we can't return before
doing the memset or we could end up using uninitialized memory in the
cleanup path.

Change-Id: Icee6be8ea22644d7f16264d9d2a0887c7145996b
CRs-Fixed: 611562
Signed-off-by: Dan Carpenter <dan.carpenter@oracle.com>
Cc: Akinobu Mita <akinobu.mita@gmail.com>
Cc: Imre Deak <imre.deak@intel.com>
Cc: Tejun Heo <tj@kernel.org>
Cc: Daniel Vetter <daniel.vetter@ffwll.ch>
Cc: Maxim Levitsky <maximlevitsky@gmail.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

lib: memory_alloc: Support 64-bit physical addresses

The current memory allocation code does not support physical
addresses above 32-bits, meaning that LPAE is not supported.
Change the types of the code internally to support 64-bit
physical addresses. Full 64-bit virtual addresses may not be
fully supported so this code will still need an update when
that happens.

Change-Id: I0c4a7b76784981ffcd7f4776d51e05f3592bb7b8
Signed-off-by: Laura Abbott <lauraa@codeaurora.org>

lib: genalloc: Use 64 bit types for holding allocations

genalloc may be used to allocate physical addresses in addition
to virtual addresses. On LPAE based systems, physical addresses
are 64-bit which does not fit in an unsigned long. Change the
type used for allocation internally to be 64 bit to ensure that
genalloc can properly allocate physical addresses > 4GB.

Ideally this will just be a temporary workaround until either
a proper fix comes elsewhere or an alternative API is used to
manage physical memory.

Change-Id: Ib10b887730e0c6916de5d1e6f77e771c6cde14bb
Signed-off-by: Laura Abbott <lauraa@codeaurora.org>

lib: vsprintf: Add %pa format specifier for phys_addr_t types

Add the %pa format specifier for printing a phys_addr_t
type and its derivative types (such as resource_size_t),
since the physical address size on some platforms can vary
based on build options, regardless of the native integer
type.

Change-Id: I2ba0003d689a9a2bd13f1a1e2d897b6eacc5d224
Signed-off-by: Stepan Moskovchenko <stepanm@codeaurora.org>

lib: qmi: Introduce QMI Encode/Decode library

Introduce Encode/Decode Library to perform QMI message marshaling.
The QMI Encode/Decode Library encodes the kernel C data structures into
QMI wire format and decodes the messages in QMI wire format into kernel
C structures.

Change-Id: Ib443e697dafedeac8a790de9a3a8ed4a8444082f
Signed-off-by: Karthikeyan Ramasubramanian <kramasub@codeaurora.org>

lib: qmi: Add logging to debug QMI Encode/Decode Library

Add logging macros to QMI Encode/Decode Library to enable debugging.
Add a kernel config to enable/disable the logging.

Change-Id: I9d8b44b2e75f281067161618f2a02a660c4d6812
Signed-off-by: Karthikeyan Ramasubramanian <kramasub@codeaurora.org>

lib: qmi: Add check to avoid out of bound memory access

If QMI clients pass an invalid maximum message length parameter, the
QMI message encode operation may perform an out of bound encode buffer
access.

Add a check in the QMI message encode operation to avoid out of bound
buffer access.

CRs-Fixed: 437329
Change-Id: I9d16078fade8160f327a8a77aea6c2a8e66b3127
Signed-off-by: Karthikeyan Ramasubramanian <kramasub@codeaurora.org>

lib: qmi: Add api to verify maximum length of a QMI message

The new API is added to verify the maximum length of a QMI message
embedded inside the message descriptor matches the expected maximum
length of the concerned QMI message. The expected maximum length of
the QMI message is calculated using the message descriptor which
describes all the elements in the structure.

Change-Id: I09602df410d9891d60f1502245ad055653f8f0f7
Signed-off-by: Karthikeyan Ramasubramanian <kramasub@codeaurora.org>

lib: qmi: Add config string

Adding config string allows a config item to be enabled either through
defconfig or through menuconfig.

Change-Id: I0d1ca3f1fc4c9ce45c433292af8ffbe3482a450b
Signed-off-by: Karthikeyan Ramasubramanian <kramasub@codeaurora.org>

lib: Pass the correct align offset to bitmap_find_next_zero_area_off

bitmap_find_next_zero_area_off requires everything to be given in terms
of bits. genpool no longer keeps track of everything in terms of bits
so the start address must be shifted before passing to
bitmap_find_next_zero_area_off. Without this, if the start address
is unaligned, the code will not take this into account.

Change-Id: I49e3dba51c48e2f97b03b21304e1258e83881c6b
Signed-off-by: Laura Abbott <lauraa@codeaurora.org>

spinlock_debug: Fix mismerge

This file was mismerged in the 3.4 kernel upgrade. We shouldn't
print the lockup twice.

Change-Id: If09a07d8b6c570632e1abac0a23c3ed203cd3ced
Signed-off-by: Stephen Boyd <sboyd@codeaurora.org>
sched/debug: Make sysrq prints of sched debug data optional

Calls to sysrq_sched_debug_show() can yield rather verbose output
which contributes to log spew and, under heavy load, may increase
the chances of a watchdog bark.

Make printing of this data optional with the introduction of a
new Kconfig, CONFIG_SYSRQ_SCHED_DEBUG.

Change-Id: I5f54d901d0dea403109f7ac33b8881d967a899ed
Signed-off-by: Matt Wagantall <mattw@codeaurora.org>
kernel/lib: add additional debug capabilites for data corruption

Data corruptions in the kernel often end up in system crashes that
are easier to debug closer to the time of detection. Specifically,
if we do not panic immediately after lock or list corruptions have been
detected, the problem context is lost in the ensuing system mayhem.
Add support for allowing system crash immediately after such corruptions
are detected. The CONFIG option controls the enabling/disabling of the
feature.

Change-Id: I9b2eb62da506a13007acff63e85e9515145909ff
Signed-off-by: Syed Rameez Mustafa <rameezmustafa@codeaurora.org>
defconfig: set ROW governor as default
random32: *merged updates from* korg/linux-3.14.y

prandom: introduce prandom_bytes() and prandom_bytes_state()

Add functions to get the requested number of pseudo-random bytes.

The difference from get_random_bytes() is that it generates pseudo-random
numbers by prandom_u32().  It doesn't consume the entropy pool, and the
sequence is reproducible if the same rnd_state is used.  So it is suitable
for generating random bytes for testing.

Signed-off-by: Akinobu Mita <akinobu.mita@gmail.com>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Artem Bityutskiy <dedekind1@gmail.com>
Cc: Adrian Hunter <adrian.hunter@intel.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Cc: Eilon Greenstein <eilong@broadcom.com>
Cc: David Laight <david.laight@aculab.com>
Cc: Michel Lespinasse <walken@google.com>
Cc: Robert Love <robert.w.love@intel.com>
Cc: Valdis Kletnieks <valdis.kletnieks@vt.edu>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

random32: rename random32 to prandom

This renames all random32 functions to have 'prandom_' prefix as follows:

  void prandom_seed(u32 seed);	/* rename from srandom32() */
  u32 prandom_u32(void);		/* rename from random32() */
  void prandom_seed_state(struct rnd_state *state, u64 seed);
  				/* rename from prandom32_seed() */
  u32 prandom_u32_state(struct rnd_state *state);
  				/* rename from prandom32() */

The purpose of this renaming is to prevent some kernel developers from
assuming that prandom32() and random32() might imply that only
prandom32() was the one using a pseudo-random number generator by
prandom32's "p", and the result may be a very embarassing security
exposure.  This concern was expressed by Theodore Ts'o.

And furthermore, I'm going to introduce new functions for getting the
requested number of pseudo-random bytes.  If I continue to use both
prandom32 and random32 prefixes for these functions, the confusion
is getting worse.

As a result of this renaming, "prandom_" is the common prefix for
pseudo-random number library.

Currently, srandom32() and random32() are preserved because it is
difficult to rename too many users at once.

Signed-off-by: Akinobu Mita <akinobu.mita@gmail.com>
Cc: "Theodore Ts'o" <tytso@mit.edu>
Cc: Robert Love <robert.w.love@intel.com>
Cc: Michel Lespinasse <walken@google.com>
Cc: Valdis Kletnieks <valdis.kletnieks@vt.edu>
Cc: David Laight <david.laight@aculab.com>
Cc: Adrian Hunter <adrian.hunter@intel.com>
Cc: Artem Bityutskiy <dedekind1@gmail.com>
Cc: David Woodhouse <dwmw2@infradead.org>
Cc: Eilon Greenstein <eilong@broadcom.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>

random32: add periodic reseeding

The current Tausworthe PRNG is never reseeded with truly random data after
the first attempt in late_initcall. As this PRNG is used for some critical
random data as e.g. UDP port randomization we should try better and reseed
the PRNG once in a while with truly random data from get_random_bytes().

When we reseed with prandom_seed we now make also sure to throw the first
output away. This suffices the reseeding procedure.

The delay calculation is based on a proposal from Eric Dumazet.

Joint work with Daniel Borkmann.

Cc: Eric Dumazet <eric.dumazet@gmail.com>
Cc: Theodore Ts'o <tytso@mit.edu>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Signed-off-by: David S. Miller <davem@davemloft.net>

random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized

The Tausworthe PRNG is initialized at late_initcall time. At that time the
entropy pool serving get_random_bytes is not filled sufficiently. This
patch adds an additional reseeding step as soon as the nonblocking pool
gets marked as initialized.

On some machines it might be possible that late_initcall gets called after
the pool has been initialized. In this situation we won't reseed again.

(A call to prandom_seed_late blocks later invocations of early reseed
attempts.)

Joint work with Daniel Borkmann.

Cc: Eric Dumazet <eric.dumazet@gmail.com>
Cc: Theodore Ts'o <tytso@mit.edu>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Acked-by: "Theodore Ts'o" <tytso@mit.edu>
Signed-off-by: David S. Miller <davem@davemloft.net>

random32: upgrade taus88 generator to taus113 from errata paper

Since we use prandom*() functions quite often in networking code
i.e. in UDP port selection, netfilter code, etc, upgrade the PRNG
from Pierre L'Ecuyer's original paper "Maximally Equidistributed
Combined Tausworthe Generators", Mathematics of Computation, 65,
213 (1996), 203--213 to the version published in his errata paper [1].

The Tausworthe generator is a maximally-equidistributed generator,
that is fast and has good statistical properties [1].

The version presented there upgrades the 3 state LFSR to a 4 state
LFSR with increased periodicity from about 2^88 to 2^113. The
algorithm is presented in [1] by the very same author who also
designed the original algorithm in [2].

Also, by increasing the state, we make it a bit harder for attackers
to "guess" the PRNGs internal state. See also discussion in [3].

Now, as we use this sort of weak initialization discussed in [3]
only between core_initcall() until late_initcall() time [*] for
prandom32*() users, namely in prandom_init(), it is less relevant
from late_initcall() onwards as we overwrite seeds through
prandom_reseed() anyways with a seed source of higher entropy, that
is, get_random_bytes(). In other words, a exhaustive keysearch of
96 bit would be needed. Now, with the help of this patch, this
state-search increases further to 128 bit. Initialization needs
to make sure that s1 > 1, s2 > 7, s3 > 15, s4 > 127.

taus88 and taus113 algorithm is also part of GSL. I added a test
case in the next patch to verify internal behaviour of this patch
with GSL and ran tests with the dieharder 3.31.1 RNG test suite:

$ dieharder -g 052 -a -m 10 -s 1 -S 4137730333 #taus88
$ dieharder -g 054 -a -m 10 -s 1 -S 4137730333 #taus113

With this seed configuration, in order to compare both, we get
the following differences:

algorithm                 taus88           taus113
rands/second [**]         1.61e+08         1.37e+08
sts_serial(4, 1st run)    WEAK             PASSED
sts_serial(9, 2nd run)    WEAK             PASSED
rgb_lagged_sum(31)        WEAK             PASSED

We took out diehard_sums test as according to the authors it is
considered broken and unusable [4]. Despite that and the slight
decrease in performance (which is acceptable), taus113 here passes
all 113 tests (only rgb_minimum_distance_5 in WEAK, the rest PASSED).
In general, taus/taus113 is considered "very good" by the authors
of dieharder [5].

The papers [1][2] states a single warm-up step is sufficient by
running quicktaus once on each state to ensure proper initialization
of ~s_{0}:

Our selection of (s) according to Table 1 of [1] row 1 holds the
condition L - k <= r - s, that is,

  (32 32 32 32) - (31 29 28 25) <= (25 27 15 22) - (18 2 7 13)

with r = k - q and q = (6 2 13 3) as also stated by the paper.
So according to [2] we are safe with one round of quicktaus for
initialization. However we decided to include the warm-up phase
of the PRNG as done in GSL in every case as a safety net. We also
use the warm up phase to make the output of the RNG easier to
verify by the GSL output.

In prandom_init(), we also mix random_get_entropy() into it, just
like drivers/char/random.c does it, jiffies ^ random_get_entropy().
random-get_entropy() is get_cycles(). xor is entropy preserving so
it is fine if it is not implemented by some architectures.

Note, this PRNG is *not* used for cryptography in the kernel, but
rather as a fast PRNG for various randomizations i.e. in the
networking code, or elsewhere for debugging purposes, for example.

[*]: In order to generate some "sort of pseduo-randomness", since
get_random_bytes() is not yet available for us, we use jiffies and
initialize states s1 - s3 with a simple linear congruential generator
(LCG), that is x <- x * 69069; and derive s2, s3, from the 32bit
initialization from s1. So the above quote from [3] accounts only
for the time from core to late initcall, not afterwards.
[**] Single threaded run on MacBook Air w/ Intel Core i5-3317U

 [1] http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme2.ps
 [2] http://www.iro.umontreal.ca/~lecuyer/myftp/papers/tausme.ps
 [3] http://thread.gmane.org/gmane.comp.encryption.general/12103/
 [4] http://code.google.com/p/dieharder/source/browse/trunk/libdieharder/diehard_sums.c?spec=svn490&r=490#20
 [5] http://www.phy.duke.edu/~rgb/General/dieharder.php

Joint work with Hannes Frederic Sowa.

Cc: Florian Weimer <fweimer@redhat.com>
Cc: Theodore Ts'o <tytso@mit.edu>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
Signed-off-by: David S. Miller <davem@davemloft.net>

random32: add test cases for taus113 implementation

We generated a battery of 100 test cases from GSL taus113 implemention
and compare the results from a particular seed and a particular
iteration with our implementation in the kernel. We have verified on
32 and 64 bit machines that our taus113 kernel implementation gives
same results as GSL taus113 implementation:

  [    0.147370] prandom: seed boundary self test passed
  [    0.148078] prandom: 100 self tests passed

This is a Kconfig option that is disabled on default, just like the
crc32 init selftests in order to not unnecessary slow down boot process.
We also refactored out prandom_seed_very_weak() as it's now used in
multiple places in order to reduce redundant code.

GSL code we used for generating test cases:

  int i, j;
  srand(time(NULL));
  for (i = 0; i < 100; ++i) {
    int iteration = 500 + (rand() % 500);
    gsl_rng_default_seed = rand() + 1;
    gsl_rng *r = gsl_rng_alloc(gsl_rng_taus113);
    printf("\t{ %lu, ", gsl_rng_default_seed);
    for (j = 0; j < iteration - 1; ++j)
      gsl_rng_get(r);
    printf("%u, %lu },\n", iteration, gsl_rng_get(r));
    gsl_rng_free(r);
  }

Joint work with Hannes Frederic Sowa.

Cc: Florian Weimer <fweimer@redhat.com>
Cc: Theodore Ts'o <tytso@mit.edu>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
Signed-off-by: David S. Miller <davem@davemloft.net>

random32: add __init prefix to prandom_start_seed_timer

We only call that in functions annotated with __init, so add __init
prefix in prandom_start_seed_timer() as well, so that the kernel can
make use of this hint and we can possibly free up resources after it's
usage. And since it's an internal function rename it to
__prandom_start_seed_timer().

Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
Signed-off-by: David S. Miller <davem@davemloft.net>

random32: use msecs_to_jiffies for reseed timer

Use msecs_to_jiffies, for these calculations as different HZ
considerations are taken into account for conversion of the timer
shot, and also it makes the code more readable.

Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Signed-off-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
Signed-off-by: David S. Miller <davem@davemloft.net>

random32: avoid attempt to late reseed if in the middle of seeding

Commit 4af712e8df ("random32: add prandom_reseed_late() and call when
nonblocking pool becomes initialized") has added a late reseed stage
that happens as soon as the nonblocking pool is marked as initialized.

This fails in the case that the nonblocking pool gets initialized
during __prandom_reseed()'s call to get_random_bytes(). In that case
we'd double back into __prandom_reseed() in an attempt to do a late
reseed - deadlocking on 'lock' early on in the boot process.

Instead, just avoid even waiting to do a reseed if a reseed is already
occuring.

Fixes: 4af712e8df99 ("random32: add prandom_reseed_late() and call when nonblocking pool becomes initialized")
Signed-off-by: Sasha Levin <sasha.levin@oracle.com>
Acked-by: Hannes Frederic Sowa <hannes@stressinduktion.org>
Signed-off-by: Daniel Borkmann <dborkman@redhat.com>
Signed-off-by: David S. Miller <davem@davemloft.net>

random: allow architectures to optionally define random_get_entropy()

Allow architectures which have a disabled get_cycles() function to
provide a random_get_entropy() function which provides a fine-grained,
rapidly changing counter that can be used by the /dev/random driver.

For example, an architecture might have a rapidly changing register
used to control random TLB cache eviction, or DRAM refresh that
doesn't meet the requirements of get_cycles(), but which is good
enough for the needs of the random driver.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
Cc: stable@vger.kernel.org
ext4: use prandom_u32() instead of get_random_bytes()

Many of the uses of get_random_bytes() do not actually need
cryptographically secure random numbers.  Replace those uses with a
call to prandom_u32(), which is faster and which doesn't consume
entropy from the /dev/random driver.

Signed-off-by: "Theodore Ts'o" <tytso@mit.edu>
defconfig: disabled HIGHMEM
drivers/cpufreq: conservative: simplified SAMPLING_TIME determination

...because simple things can be good things, too.

oh...and because maybe someone seriously wanna use this governor on his device with any lower sampling_rate than 2000000 *lol*
Makefile: supressing false-positive compiler warnings

...for variables, which can be used uninitialized