block: Added ROW io scheduler.
https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/22295684c4302312267b8ceee89537620288417c
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.

With following patches:
1.Correct minimum values of ROW tunable parameters
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/4b0ed19eef8f85bbb4f7ca8f5a186f1f3fd3d8f7
  The ROW scheduling algorithm exposes several tunable parameters.
  This patch updates the minimum allowed values for those parameters.

2.Fix forced dispatch
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/ede0d75ed505db748dcd42553dc765ce0a90f3ba
  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.

3.Adding support for reinsert already dispatched req
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/5defc31da869076d5698b3eaaeb1b5f28de2fb3c
  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.

4.Fix idling mechanism in ROW
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/0421ec412ab37f38fd480a95bf46468e146cd509
  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

5.Add support for urgent request handling
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/e67c4d4bf4eab01db4fb3dc4fff27ec0643fd4cd
  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.

6.Add some debug information on ROW queues
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/52fe9e5776780489c2b75fbe45a71623846d7e10
  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).

7.Insert dispatch_quantum into struct row_queue
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/7b625d10cbd0c9e4036e9e20573ac630074bc0e0
  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.

8.Fix sysfs functions - idle_time conversion
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/fa1386f5a3a89022e9b7bcdf5f23d27b8c3fa5ec
  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.

9.Aggregate row_queue parameters to one structure
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/aa04614cdc837bb8ae41c2a488928357e838b008
  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

10.Dispatch requests according to their io-priority
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/d5d918d7074948611465c52d6ced2a8b89bd154a
  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.

11.Idling mechanism re-factoring
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/2e44b5dc1573d91085bc4d1b9510d5cef4fb69e6
  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).

12.Don't notify URGENT if there are un-completed urgent req
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/1661155e32409d7a870f10d2c4f233a2b73fc5ed
  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.

13.Update initial values of ROW data structures
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/01b421c228f49b96e344893c21a2120e6ccf2c53
  This patch sets the initial values of internal ROW parameters.

14.Re-design urgent request notification mechanism
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/03e4e88d0956f1ed3928691630d165bf5d233a2c
  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.

15.Prevent starvation of regular priority by high priority
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/018a5aade86153e9156901e712098e2baf97ea86
  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.

16.Update sysfs functions
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/8852c4db804ed1f73efad6de3dc32c5cf2fff0db
  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.

17.Fix starvation tolerance values
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/cb97d9911821289799d8716052ec0925383c3d9f
  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.

18.idling triggered by readahead pages
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/e33e599a5527e24d2a41252937d625dac4e86cdb
  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).

19.Change hrtimer_cancel to hrtimer_try_to_cancel
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/be557c3f9b8944509293955da9be62bb292787e6
  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.

20.Remove warning massage from add_request
  https://github.com/AndreiLux/Perseus-UNIVERSAL5410/commit/6e42d2a595838d1eb12c24e4cf1675e341f98eb1
  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.