block: cgroups, kconfig, build bits for BFQ-v7-3.13

Update Kconfig.iosched and do the related Makefile changes to include
kernel configuration options for BFQ. Also add the bfqio controller
to the cgroups subsystem.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
block: introduce the BFQ-v7 I/O sched for 3.13

Add the BFQ-v7 I/O scheduler to 3.13.
The general structure is borrowed from CFQ, as much of the code for
handling I/O contexts Over time, several useful features have been
ported from CFQ as well (details in the changelog in README.BFQ). A
(bfq_)queue is associated to each task doing I/O on a device, and each
time a scheduling decision has to be made a queue is selected and served
until it expires.

    - Slices are given in the service domain: tasks are assigned
      budgets, measured in number of sectors. Once got the disk, a task
      must however consume its assigned budget within a configurable
      maximum time (by default, the maximum possible value of the
      budgets is automatically computed to comply with this timeout).
      This allows the desired latency vs "throughput boosting" tradeoff
      to be set.

    - Budgets are scheduled according to a variant of WF2Q+, implemented
      using an augmented rb-tree to take eligibility into account while
      preserving an O(log N) overall complexity.

    - A low-latency tunable is provided; if enabled, both interactive
      and soft real-time applications are guaranteed a very low latency.

    - Latency guarantees are preserved also in the presence of NCQ.

    - Also with flash-based devices, a high throughput is achieved
      while still preserving latency guarantees.

    - BFQ features Early Queue Merge (EQM), a sort of fusion of the
      cooperating-queue-merging and the preemption mechanisms present
      in CFQ. EQM is in fact a unified mechanism that tries to get a
      sequential read pattern, and hence a high throughput, with any
      set of processes performing interleaved I/O over a contiguous
      sequence of sectors.

    - BFQ supports full hierarchical scheduling, exporting a cgroups
      interface.  Since each node has a full scheduler, each group can
      be assigned its own weight.

    - If the cgroups interface is not used, only I/O priorities can be
      assigned to processes, with ioprio values mapped to weights
      with the relation weight = IOPRIO_BE_NR - ioprio.

    - ioprio classes are served in strict priority order, i.e., lower
      priority queues are not served as long as there are higher
      priority queues.  Among queues in the same class the bandwidth is
      distributed in proportion to the weight of each queue. A very
      thin extra bandwidth is however guaranteed to the Idle class, to
      prevent it from starving.

Signed-off-by: Paolo Valente <paolo.valente@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
block, bfq: add Early Queue Merge (EQM) to BFQ-v7 for 3.13.0

A set of processes may happen  to  perform interleaved reads, i.e., requests
whose union would give rise to a  sequential read  pattern.  There are two
typical  cases: in the first  case,   processes  read  fixed-size chunks of
data at a fixed distance from each other, while in the second case processes
may read variable-size chunks at  variable distances. The latter case occurs
for  example with  KVM, which  splits the  I/O generated  by the  guest into
multiple chunks,  and lets these chunks  be served by a  pool of cooperating
processes,  iteratively  assigning  the  next  chunk of  I/O  to  the first
available  process. CFQ  uses actual  queue merging  for the  first type  of
rocesses, whereas it  uses preemption to get a sequential  read pattern out
of the read requests  performed by the second type of  processes. In the end
it uses  two different  mechanisms to  achieve the  same goal: boosting the
throughput with interleaved I/O.

This patch introduces  Early Queue Merge (EQM), a unified mechanism to get a
sequential  read pattern  with both  types of  processes. The  main idea  is
checking newly arrived requests against the next request of the active queue
both in case of actual request insert and in case of request merge. By doing
so, both the types of processes can be handled by just merging their queues.
EQM is  then simpler and  more compact than the  pair of mechanisms used in
CFQ.

Finally, EQM  also preserves the  typical low-latency properties of BFQ, by
properly restoring the weight-raising state of  a queue when it gets back to
a non-merged state.

Signed-off-by: Mauro Andreolini <mauro.andreolini@unimore.it>
Signed-off-by: Arianna Avanzini <avanzini.arianna@gmail.com>
Reviewed-by: Paolo Valente <paolo.valente@unimore.it>
block: make BFQ the default I/O scheduler

Conflicts:
	block/Kconfig.iosched
block: Switch from BFQ-v7 for 3.13.0 to BFQ-v7r1 for 3.13.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.13.0 to BFQ-v7r2 for 3.13.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>
bfs: Tweak configs and restore hidden config options
bfs: Add autoiso for X
Add exfat driver

From https://github.com/rxrz/exfat-nofuse.git
State 1691cda
exFAT Kconfig and build bits
net: allow TCP YeAH configuration as default congestion control
uksm-0.1.2.2-for-v3.13.patch

from http://kerneldedup.org/projects/uksm/download/
hostap: restore power setting value when lost due to F/W bug

source: openwrt/patches-2.6.38/903-hostap_txpower.patch
x86: Enable monitor/mwait on Intel if BIOS hasn't already

My Intel DQ67SW (latest BIOS) disables monitor/mwait on the boot CPU
if TXT is enabled.  We're lucky that the system works at all, since
the feature is still enabled on other CPUs.

The obvious fix is to just re-enable it ourselves.

Signed-off-by: Andy Lutomirski <luto@mit.edu>
net: combat buffer bloat

Set tx_queue_len to 50 (FreeBSD default) from 1000 to reduce latencies.  Set
tcp_ecn to 1 to force enable Explicit Congestion Notification.  These two
changes should make a positive impact network performance.  Possible drop in
throughput with 1 gbit and faster networks.

net: restore tcp_ecn default

Forcing ECN breaks some Cisco routers with SPI firewall enabled.
x86: Enable fast strings on Intel if BIOS hasn't already

Intel SDM volume 3A, 8.4.2 says:

  Software can disable fast-string operation by clearing the
  fast-string-enable bit (bit 0) of IA32_MISC_ENABLE MSR.
  However, Intel recomments that system software always enable
  fast-string operation.

The Intel DQ67SW board (with latest BIOS) disables fast string
operations if TXT is enabled.  A Lenovo X220 disables it regardless
of TXT setting.  I doubt I'm the only person with a dumb BIOS like
this.

Signed-off-by: Andy Lutomirski <luto@amacapital.net>
BFS tweaks
Updates to 3.13.11, final commit