block: Switch from BFQ-v6r2 for 3.11.0 to BFQ-v7 for 3.11.0 - first part

Improvements:

- IMPROVEMENT: In the presence of weight-raised queues and if the
  device is NCQ-enabled, device idling is now disabled for non-raised
  readers, i.e., for their associated sync queues. Hence a sync queue
  is expired immediately if it becomes empty, and a new queue is
  served.  As explained in detail in the papers about BFQ, not idling
  the device for sync queues when the latter become empty causes BFQ to
  assign higher timestamps to these queues when they get backlogged
  again, and hence to serve these queues less frequently. This fact,
  plus to the fact that, because of the immediate expiration itself,
  these queues get less service while they are granted access to the
  disk, reduces the relative rate at which the processes associated to
  these queues ask for requests from the I/O request pool. If the pool
  is saturated, as it happens, in the presence of write hogs, reducing
  the above relative rate increases the probability that a request is
  available (soon) in the pool when a weight-raised process needs it.
  This change does seem to mitigate the typical starvation problems
  that occur in the presence of write hogs and NCQ, and hence to
  guarantee a higher application and system responsiveness in these
  hostile scenarios.
- IMPROVEMENT/BUGFIX: Introduced a new classification rule to the soft
  real-time heuristic, which takes into account also the isochronous
  nature of such applications. The computation of next_start has been
  fixed as well. Now it is correctly done from the time of the last
  transition from idle to backlogged; the next_start is therefore
  computed from the service received by the queue from its last
  transition from idle to backlogged. Finally, the code which
  preserved weight-raising for a soft real-time queue even with no
  idle->backlogged transition has been removed.
- IMPROVEMENT/BUGFIX: Keep disk idling also for NCQ-provided
  rotational devices, which boosts the throughput on NCQ-enabled
  rotational devices.
- BUGFIX: The budget-timeout condition in the bfq_rq_enqueued() function
  was checked only if the request is large enough to provoke an unplug. As
  a consequence, for a process always issuing small I/O requests the
  budget timeout was never checked. The queue associated to the process
  therefore expired only when its budget was exhausted, even if the
  queue had already incurred a budget timeout from a while.
  This fix lets a queue be checked for budget timeout at each request
  enqueue, and, if needed, expires the queue accordingly even if the
  request is small.
- BUGFIX: Make sure that weight-raising is resumed for a split queue,
  if it was merged when already weight-raised.
- MINOR BUGFIX: Let bfq_end_raising_async() correctly end weight-raising
  also for the queues belonging to the root group.
- IMPROVEMENT: Get rid of the some_coop_idle flag, which in its turn
  was used to decide whether to disable idling for an in-service
  shared queue whose seek mean decreased. In fact, disabling idling
  for such a queue turned out to be useless.
- CODE IMPROVEMENT: The bfq_bfqq_must_idle() function and the
  bfq_select_queue() function may not change the current in-service
  queue in various cases. We have cleaned up the involved conditions,
  by factoring out the common parts and getting rid of the useless
  ones.
- MINOR CODE IMPROVEMENT: The idle_for_long_time condition in the
  bfq_add_rq_rb() function should be evaluated only on an
  idle->backlogged transition. Now the condition is set to false
  by default, evaluating it only if the queue was not busy on a
  request insertion.
- MINOR CODE IMPROVEMENT: Added a comment describing the rationale
  behind the condition evalutated in the function
  bfq_bfqq_must_not_expire().

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Tested-by: Alexander Spyridakis <a.spyridakis@virtualopensystems.com>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
block: Switch from BFQ-v6r2 for 3.11.0 to BFQ-v7 for 3.11.0 - second part

Improvements:

- An application must be non-greedy to be deemed as soft real-time (it is
  one of the conditions to meet). The condition is checked by controlling
  whether a long-enough time interval, by default HZ/125 seconds, elapsed
  from when the queue associated to the application became idle, to when
  the queue becomes backlogged again. Elapsed time is measured in
  jiffies.
  This control easily generates false positives in the following two
  cases (especially if both cases occur):
  1) If HZ is so low that the duration of a jiffie is comparable to or
     higher than the above reference time interval. This happens, e.g.,
     on slow devices with HZ=100.
  2) If jiffies, instead of increasing at a constant rate, may stop
     increasing for some time, then suddenly 'jump' by several units to
     recover the lost increments. This seems to happen, e.g., in virtual
     machines.
  This commit adds a few jiffies to the above reference time interval.
  We found the number of jiffies to add experimentally. In particular,
  according to our experiments, the number of jiffies added by this
  commit seems to make the filter quite precise also in embedded systems
  and KVM/QEMU virtual machines.

Signed-off-by: Paolo Valente <p.valente@virtualopensystems.com>
Signed-off-by: Alexander Spyridakis <a.spyridakis@virtualopensystems.com>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
block: Switch from BFQ-v7 for 3.11.0 to BFQ-v7r1 for 3.11.0

In a code-cleanup phase, we introduced the following errors in the
heuristic for detecting when an application is soft real-time:
. We started (properly) to use the macro time_is_before_jiffies() to
  take wraparound issues into account, but such a macro easily returns
  anomalous results if its argument is equal to the value that we used
  as an approximation of 'infinity', namely ((unsigned long) (-1)).
  The consequence was that the logical expression used to determine
  whether a queue belongs to a soft real-time application often yielded
  an incorrect result. In the end, some application happened to be
  incorrectly deemed as soft real-time and hence weight-raised. This
  affected both throughput and latency guarantees.
. In an attempt to use the above macro in a logical expression we made a
  scriverner's error.

In addition, we realized that:
. On the expiration of a queue, the condition that allowed a
  weight-raising period to start, in case the queueu was soft
  real-time, was not the most general one. In particular, this could
  uncorrectly prevent an empty queue from being deemed as soft
  real-time.
. Jiffies-comparison macros were not used in the following cases, whereas
  they had to:
  . to establish whether an application initially deemed as interactive
    is now meeting the requirements for being classified as soft
    real-time;
  . to determine if a weight-raising period must be ended.
. The type of the time quantities used in the weight-raising heuristics
  was u64, whereas the type of the time (jiffies) is unsigned long.
. There were some typos in the wrais-related log messages.
. The next_active and active_entity field of the bfq_sched_data data
  structure did not follow the new naming convention introduced with v7.

This commit tries to address and fix all the above issues and problems.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
block: Switch from BFQ-v7r1 for 3.11.0 to BFQ-v7r2 for 3.11.0

1) BUGFIX/IMPROVEMENT. One of the requirements for an application to be
   deemed as soft real-time is that it issues its requests in batches, and
   stops doing I/O for a well-defined amount of time before issuing a new
   batch. Imposing this minimum idle time allows BFQ to filter out I/O-bound
   applications that may otherwise be incorrectly deemed as soft real-time
   (under the circumstances described in detail in the comments to the
   function bfq_bfqq_softrt_next_start()). Unfortunately, BFQ could however
   start counting this idle time from two different events: either from the
   expiration of the queue, if all requests of the queue had also been already
   completed when the queue expired, or, if the previous condition did not
   hold, from the first completion of one of the still outstanding requests.
   In the second case, an application had more chances to be deemed as soft
   real-time.
   Actually, there was no reason for this differentiated treatment. We
   addressed this issue by defining more precisely the above requirement for
   an application to be deemed as soft real-time, and changing the code
   consequently: a well-defined amount of time must elapse between the
   completion of *all the requests* of the current pending batch and the
   issuing of the first request of the next batch (this is, in the end, what
   happens with a true soft real-time application). This change further
   reduced false positives, and, as such, improved responsiveness and reduced
   latency for actual soft real-time applications.
2) CODE IMPROVEMENT. We cleaned up the code a little bit and addressed
   some issues pointed out by the checkpatch.pl script.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
block: Switch from BFQ-v7r2 for 3.11.0 to BFQ-v7r3 for 3.11.0

. IMPROVEMENT: Improved throughput boosting with NCQ-capable HDDs and
  random workloads. The mechanism that further boosts throghput with
  these devices and workloads is activated only in the cases where it
  does not cause any violation of throughput-distribution and latency
  guarantees.
. IMPROVEMENT: Generalized the computation of the parameters of the
  low-latency heuristic for interactive applications, so as to fit also
  slower storage devices. The purpose of this improvement is to preserve
  low-latency guarantees for interactive applications also on slower
  devices, such as portable hard disks, multimedia and SD cards.
. BUGFIX: Re-added MODULE_LICENSE macro.
. CODE IMPROVEMENTS: Small code cleanups; introduced a coherent naming
  scheme for all identifiers related to weight raising; refactored and
  optimized a few hot paths.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Oleksandr Natalenko <oleksandr@natalenko.name>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
Reported-by: Mikhail Akushsky <namelles.one@gmail.com>
block: Switch from BFQ-v7r3 for 3.11.0 to BFQ-v7r4 for 3.11.0

. BUGFIX. Modified the code so as to be robust against late detection of
  NCQ support for a rotational device.
. BUGFIX. Removed a bug that hindered the correct throughput distribution
  on flash-based devices when not every process had to receive the same
  fraction of the throughput. This fix entailed also a little efficiency
  improvement, because it implied the removal of a short function executed
  in a hot path.
. CODESTYLE IMPROVEMENT: removed quoted strings split across lines.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Reported-by: Steven Barrett <damentz@gmail.com>
Reported-by: Claire Farron <diesal3@googlemail.com>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
block: Switch from BFQ-v7r4 for 3.11.0 to BFQ-v7r5 for 3.11.0

. IMPROVEMENT: Improve throughput boosting by idling the device
  only for processes that, in addition to perform sequential I/O,
  are I/O-bound (apart from weight-raised queues, for which idling
  is always performed to guarantee them a low latency).
. IMPROVEMENT: Improve throughput boosting by depriving processes
  that cooperate often of weight-raising.
. CODE IMPROVEMENT: Pass of improvement of the readability of both
  comments and actual code.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Tested-by: Takashi Iwai <tiwai@suse.de>
Reported-by: Pavel Machek <pavel@ucw.cz>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
block: Switch from BFQ-v7r5 for 3.11.0 to BFQ-v7r6 for 3.11.0

. IMPROVEMENT: Introduced a new mechanism that helps get the job done
  more quickly for services and applications that create or reactivate
  many parallel I/O-bound processes. Examples are systemd at boot, or
  commands such as git grep.
. CODE IMPROVEMENTS: Small code cleanups and improvements.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
block: Switch from BFQ-v7r6 for 3.11.0 to BFQ-v7r7 for 3.11.0

. BUGFIX: Prevent the OOM queue from being involved in the queue
  cooperation mechanism. In fact, since the requests temporarily
  redirected to the OOM queue could be redirected again to dedicated
  queues at any time, the state needed to correctly handle merging
  with the OOM queue would be quite complex and expensive to
  maintain. Besides, in such a critical condition as an out of
  memory, the benefits of queue merging may be little relevant, or
  even negligible.

. IMPROVEMENT: Let the OOM queue be initialized only once. Previously,
  the OOM queue was reinitialized, at each request enqueue, with the
  parameters related to the process that issued that request.
  Depending on the parameters of the processes doing I/O, this could
  easily cause the OOM queue to be moved continuously across service
  trees, or even across groups. It also caused the parameters of the
  OOM queue to be continuously reset in any case.

. CODE IMPROVEMENT. Performed some minor code cleanups, and added some
  BUG_ON()s that, if the weight of an entity becomes inconsistent,
  should better help understand why.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
Reported-by: Hector Martin <hector@marcansoft.com>
EXTRAVERSION updated