1. 09 8月, 2017 1 次提交
  2. 19 4月, 2017 2 次提交
    • P
      block, bfq: split bfq-iosched.c into multiple source files · ea25da48
      Paolo Valente 提交于
      The BFQ I/O scheduler features an optimal fair-queuing
      (proportional-share) scheduling algorithm, enriched with several
      mechanisms to boost throughput and reduce latency for interactive and
      real-time applications. This makes BFQ a large and complex piece of
      code. This commit addresses this issue by splitting BFQ into three
      main, independent components, and by moving each component into a
      separate source file:
      1. Main algorithm: handles the interaction with the kernel, and
      decides which requests to dispatch; it uses the following two further
      components to achieve its goals.
      2. Scheduling engine (Hierarchical B-WF2Q+ scheduling algorithm):
      computes the schedule, using weights and budgets provided by the above
      component.
      3. cgroups support: handles group operations (creation, destruction,
      move, ...).
      Signed-off-by: NPaolo Valente <paolo.valente@linaro.org>
      Signed-off-by: NJens Axboe <axboe@fb.com>
      ea25da48
    • P
      block, bfq: introduce the BFQ-v0 I/O scheduler as an extra scheduler · aee69d78
      Paolo Valente 提交于
      We tag as v0 the version of BFQ containing only BFQ's engine plus
      hierarchical support. BFQ's engine is introduced by this commit, while
      hierarchical support is added by next commit. We use the v0 tag to
      distinguish this minimal version of BFQ from the versions containing
      also the features and the improvements added by next commits. BFQ-v0
      coincides with the version of BFQ submitted a few years ago [1], apart
      from the introduction of preemption, described below.
      
      BFQ is a proportional-share I/O scheduler, whose general structure,
      plus a lot of code, are borrowed from CFQ.
      
      - Each process doing I/O on a device is associated with a weight and a
        (bfq_)queue.
      
      - BFQ grants exclusive access to the device, for a while, to one queue
        (process) at a time, and implements this service model by
        associating every queue with a budget, measured in number of
        sectors.
      
        - After a queue is granted access to the device, the budget of the
          queue is decremented, on each request dispatch, by the size of the
          request.
      
        - The in-service queue is expired, i.e., its service is suspended,
          only if one of the following events occurs: 1) the queue finishes
          its budget, 2) the queue empties, 3) a "budget timeout" fires.
      
          - The budget timeout prevents processes doing random I/O from
            holding the device for too long and dramatically reducing
            throughput.
      
          - Actually, as in CFQ, a queue associated with a process issuing
            sync requests may not be expired immediately when it empties. In
            contrast, BFQ may idle the device for a short time interval,
            giving the process the chance to go on being served if it issues
            a new request in time. Device idling typically boosts the
            throughput on rotational devices, if processes do synchronous
            and sequential I/O. In addition, under BFQ, device idling is
            also instrumental in guaranteeing the desired throughput
            fraction to processes issuing sync requests (see [2] for
            details).
      
            - With respect to idling for service guarantees, if several
              processes are competing for the device at the same time, but
              all processes (and groups, after the following commit) have
              the same weight, then BFQ guarantees the expected throughput
              distribution without ever idling the device. Throughput is
              thus as high as possible in this common scenario.
      
        - Queues are scheduled according to a variant of WF2Q+, named
          B-WF2Q+, and implemented using an augmented rb-tree to preserve an
          O(log N) overall complexity.  See [2] for more details. B-WF2Q+ is
          also ready for hierarchical scheduling. However, for a cleaner
          logical breakdown, the code that enables and completes
          hierarchical support is provided in the next commit, which focuses
          exactly on this feature.
      
        - B-WF2Q+ guarantees a tight deviation with respect to an ideal,
          perfectly fair, and smooth service. In particular, B-WF2Q+
          guarantees that each queue receives a fraction of the device
          throughput proportional to its weight, even if the throughput
          fluctuates, and regardless of: the device parameters, the current
          workload and the budgets assigned to the queue.
      
        - The last, budget-independence, property (although probably
          counterintuitive in the first place) is definitely beneficial, for
          the following reasons:
      
          - First, with any proportional-share scheduler, the maximum
            deviation with respect to an ideal service is proportional to
            the maximum budget (slice) assigned to queues. As a consequence,
            BFQ can keep this deviation tight not only because of the
            accurate service of B-WF2Q+, but also because BFQ *does not*
            need to assign a larger budget to a queue to let the queue
            receive a higher fraction of the device throughput.
      
          - Second, BFQ is free to choose, for every process (queue), the
            budget that best fits the needs of the process, or best
            leverages the I/O pattern of the process. In particular, BFQ
            updates queue budgets with a simple feedback-loop algorithm that
            allows a high throughput to be achieved, while still providing
            tight latency guarantees to time-sensitive applications. When
            the in-service queue expires, this algorithm computes the next
            budget of the queue so as to:
      
            - Let large budgets be eventually assigned to the queues
              associated with I/O-bound applications performing sequential
              I/O: in fact, the longer these applications are served once
              got access to the device, the higher the throughput is.
      
            - Let small budgets be eventually assigned to the queues
              associated with time-sensitive applications (which typically
              perform sporadic and short I/O), because, the smaller the
              budget assigned to a queue waiting for service is, the sooner
              B-WF2Q+ will serve that queue (Subsec 3.3 in [2]).
      
      - Weights can be assigned to processes only indirectly, through I/O
        priorities, and according to the relation:
        weight = 10 * (IOPRIO_BE_NR - ioprio).
        The next patch provides, instead, a cgroups interface through which
        weights can be assigned explicitly.
      
      - If several processes are competing for the device at the same time,
        but all processes and groups have the same weight, then BFQ
        guarantees the expected throughput distribution without ever idling
        the device. It uses preemption instead. Throughput is then much
        higher in this common scenario.
      
      - 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.
      
      - If the strict_guarantees parameter is set (default: unset), then BFQ
           - always performs idling when the in-service queue becomes empty;
           - forces the device to serve one I/O request at a time, by
             dispatching a new request only if there is no outstanding
             request.
        In the presence of differentiated weights or I/O-request sizes,
        both the above conditions are needed to guarantee that every
        queue receives its allotted share of the bandwidth (see
        Documentation/block/bfq-iosched.txt for more details). Setting
        strict_guarantees may evidently affect throughput.
      
      [1] https://lkml.org/lkml/2008/4/1/234
          https://lkml.org/lkml/2008/11/11/148
      
      [2] P. Valente and M. Andreolini, "Improving Application
          Responsiveness with the BFQ Disk I/O Scheduler", Proceedings of
          the 5th Annual International Systems and Storage Conference
          (SYSTOR '12), June 2012.
          Slightly extended version:
          http://algogroup.unimore.it/people/paolo/disk_sched/bfq-v1-suite-
      							results.pdf
      Signed-off-by: NFabio Checconi <fchecconi@gmail.com>
      Signed-off-by: NPaolo Valente <paolo.valente@linaro.org>
      Signed-off-by: NArianna Avanzini <avanzini.arianna@gmail.com>
      Signed-off-by: NJens Axboe <axboe@fb.com>
      aee69d78
  3. 15 4月, 2017 1 次提交
    • O
      blk-mq: introduce Kyber multiqueue I/O scheduler · 00e04393
      Omar Sandoval 提交于
      The Kyber I/O scheduler is an I/O scheduler for fast devices designed to
      scale to multiple queues. Users configure only two knobs, the target
      read and synchronous write latencies, and the scheduler tunes itself to
      achieve that latency goal.
      
      The implementation is based on "tokens", built on top of the scalable
      bitmap library. Tokens serve as a mechanism for limiting requests. There
      are two tiers of tokens: queueing tokens and dispatch tokens.
      
      A queueing token is required to allocate a request. In fact, these
      tokens are actually the blk-mq internal scheduler tags, but the
      scheduler manages the allocation directly in order to implement its
      policy.
      
      Dispatch tokens are device-wide and split up into two scheduling
      domains: reads vs. writes. Each hardware queue dispatches batches
      round-robin between the scheduling domains as long as tokens are
      available for that domain.
      
      These tokens can be used as the mechanism to enable various policies.
      The policy Kyber uses is inspired by active queue management techniques
      for network routing, similar to blk-wbt. The scheduler monitors
      latencies and scales the number of dispatch tokens accordingly. Queueing
      tokens are used to prevent starvation of synchronous requests by
      asynchronous requests.
      
      Various extensions are possible, including better heuristics and ionice
      support. The new scheduler isn't set as the default yet.
      Signed-off-by: NOmar Sandoval <osandov@fb.com>
      Signed-off-by: NJens Axboe <axboe@fb.com>
      00e04393
  4. 28 2月, 2017 1 次提交
  5. 07 2月, 2017 1 次提交
  6. 01 2月, 2017 1 次提交
  7. 28 1月, 2017 1 次提交
  8. 27 1月, 2017 1 次提交
    • O
      blk-mq: create debugfs directory tree · 07e4fead
      Omar Sandoval 提交于
      In preparation for putting blk-mq debugging information in debugfs,
      create a directory tree mirroring the one in sysfs:
      
          # tree -d /sys/kernel/debug/block
          /sys/kernel/debug/block
          |-- nvme0n1
          |   `-- mq
          |       |-- 0
          |       |   `-- cpu0
          |       |-- 1
          |       |   `-- cpu1
          |       |-- 2
          |       |   `-- cpu2
          |       `-- 3
          |           `-- cpu3
          `-- vda
              `-- mq
                  `-- 0
                      |-- cpu0
                      |-- cpu1
                      |-- cpu2
                      `-- cpu3
      
      Also add the scaffolding for the actual files that will go in here,
      either under the hardware queue or software queue directories.
      Reviewed-by: NHannes Reinecke <hare@suse.com>
      Signed-off-by: NOmar Sandoval <osandov@fb.com>
      Signed-off-by: NJens Axboe <axboe@fb.com>
      07e4fead
  9. 18 1月, 2017 2 次提交
  10. 11 11月, 2016 2 次提交
    • J
      blk-wbt: add general throttling mechanism · e34cbd30
      Jens Axboe 提交于
      We can hook this up to the block layer, to help throttle buffered
      writes.
      
      wbt registers a few trace points that can be used to track what is
      happening in the system:
      
      wbt_lat: 259:0: latency 2446318
      wbt_stat: 259:0: rmean=2446318, rmin=2446318, rmax=2446318, rsamples=1,
                     wmean=518866, wmin=15522, wmax=5330353, wsamples=57
      wbt_step: 259:0: step down: step=1, window=72727272, background=8, normal=16, max=32
      
      This shows a sync issue event (wbt_lat) that exceeded it's time. wbt_stat
      dumps the current read/write stats for that window, and wbt_step shows a
      step down event where we now scale back writes. Each trace includes the
      device, 259:0 in this case.
      Signed-off-by: NJens Axboe <axboe@fb.com>
      e34cbd30
    • J
      block: add scalable completion tracking of requests · cf43e6be
      Jens Axboe 提交于
      For legacy block, we simply track them in the request queue. For
      blk-mq, we track them on a per-sw queue basis, which we can then
      sum up through the hardware queues and finally to a per device
      state.
      
      The stats are tracked in, roughly, 0.1s interval windows.
      
      Add sysfs files to display the stats.
      
      The feature is off by default, to avoid any extra overhead. In-kernel
      users of it can turn it on by setting QUEUE_FLAG_STATS in the queue
      flags. We currently don't turn it on if someone just reads any of
      the stats files, that is something we could add as well.
      Signed-off-by: NJens Axboe <axboe@fb.com>
      cf43e6be
  11. 19 10月, 2016 1 次提交
  12. 22 9月, 2016 1 次提交
  13. 19 9月, 2016 1 次提交
  14. 15 9月, 2016 1 次提交
  15. 09 1月, 2016 1 次提交
  16. 12 12月, 2015 1 次提交
  17. 27 9月, 2014 1 次提交
  18. 20 5月, 2014 2 次提交
  19. 19 5月, 2014 1 次提交
  20. 25 10月, 2013 1 次提交
    • J
      blk-mq: new multi-queue block IO queueing mechanism · 320ae51f
      Jens Axboe 提交于
      Linux currently has two models for block devices:
      
      - The classic request_fn based approach, where drivers use struct
        request units for IO. The block layer provides various helper
        functionalities to let drivers share code, things like tag
        management, timeout handling, queueing, etc.
      
      - The "stacked" approach, where a driver squeezes in between the
        block layer and IO submitter. Since this bypasses the IO stack,
        driver generally have to manage everything themselves.
      
      With drivers being written for new high IOPS devices, the classic
      request_fn based driver doesn't work well enough. The design dates
      back to when both SMP and high IOPS was rare. It has problems with
      scaling to bigger machines, and runs into scaling issues even on
      smaller machines when you have IOPS in the hundreds of thousands
      per device.
      
      The stacked approach is then most often selected as the model
      for the driver. But this means that everybody has to re-invent
      everything, and along with that we get all the problems again
      that the shared approach solved.
      
      This commit introduces blk-mq, block multi queue support. The
      design is centered around per-cpu queues for queueing IO, which
      then funnel down into x number of hardware submission queues.
      We might have a 1:1 mapping between the two, or it might be
      an N:M mapping. That all depends on what the hardware supports.
      
      blk-mq provides various helper functions, which include:
      
      - Scalable support for request tagging. Most devices need to
        be able to uniquely identify a request both in the driver and
        to the hardware. The tagging uses per-cpu caches for freed
        tags, to enable cache hot reuse.
      
      - Timeout handling without tracking request on a per-device
        basis. Basically the driver should be able to get a notification,
        if a request happens to fail.
      
      - Optional support for non 1:1 mappings between issue and
        submission queues. blk-mq can redirect IO completions to the
        desired location.
      
      - Support for per-request payloads. Drivers almost always need
        to associate a request structure with some driver private
        command structure. Drivers can tell blk-mq this at init time,
        and then any request handed to the driver will have the
        required size of memory associated with it.
      
      - Support for merging of IO, and plugging. The stacked model
        gets neither of these. Even for high IOPS devices, merging
        sequential IO reduces per-command overhead and thus
        increases bandwidth.
      
      For now, this is provided as a potential 3rd queueing model, with
      the hope being that, as it matures, it can replace both the classic
      and stacked model. That would get us back to having just 1 real
      model for block devices, leaving the stacked approach to dm/md
      devices (as it was originally intended).
      
      Contributions in this patch from the following people:
      
      Shaohua Li <shli@fusionio.com>
      Alexander Gordeev <agordeev@redhat.com>
      Christoph Hellwig <hch@infradead.org>
      Mike Christie <michaelc@cs.wisc.edu>
      Matias Bjorling <m@bjorling.me>
      Jeff Moyer <jmoyer@redhat.com>
      Acked-by: NChristoph Hellwig <hch@lst.de>
      Signed-off-by: NJens Axboe <axboe@kernel.dk>
      320ae51f
  21. 01 10月, 2013 1 次提交
    • P
      block: change config option name for cmdline partition parsing · 080506ad
      Paul Gortmaker 提交于
      Recently commit bab55417 ("block: support embedded device command
      line partition") introduced CONFIG_CMDLINE_PARSER.  However, that name
      is too generic and sounds like it enables/disables generic kernel boot
      arg processing, when it really is block specific.
      
      Before this option becomes a part of a full/final release, add the BLK_
      prefix to it so that it is clear in absence of any other context that it
      is block specific.
      
      In addition, fix up the following less critical items:
       - help text was not really at all helpful.
       - index file for Documentation was not updated
       - add the new arg to Documentation/kernel-parameters.txt
       - clarify wording in source comments
      Signed-off-by: NPaul Gortmaker <paul.gortmaker@windriver.com>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: Cai Zhiyong <caizhiyong@huawei.com>
      Cc: Wei Yongjun <yongjun_wei@trendmicro.com.cn>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      080506ad
  22. 12 9月, 2013 1 次提交
    • C
      block: support embedded device command line partition · bab55417
      Cai Zhiyong 提交于
      Read block device partition table from command line.  The partition used
      for fixed block device (eMMC) embedded device.  It is no MBR, save
      storage space.  Bootloader can be easily accessed by absolute address of
      data on the block device.  Users can easily change the partition.
      
      This code reference MTD partition, source "drivers/mtd/cmdlinepart.c"
      About the partition verbose reference
      "Documentation/block/cmdline-partition.txt"
      
      [akpm@linux-foundation.org: fix printk text]
      [yongjun_wei@trendmicro.com.cn: fix error return code in parse_parts()]
      Signed-off-by: NCai Zhiyong <caizhiyong@huawei.com>
      Cc: Karel Zak <kzak@redhat.com>
      Cc: "Wanglin (Albert)" <albert.wanglin@huawei.com>
      Cc: Marius Groeger <mag@sysgo.de>
      Cc: David Woodhouse <dwmw2@infradead.org>
      Cc: Jens Axboe <axboe@kernel.dk>
      Cc: Brian Norris <computersforpeace@gmail.com>
      Cc: Artem Bityutskiy <dedekind@infradead.org>
      Signed-off-by: NWei Yongjun <yongjun_wei@trendmicro.com.cn>
      Signed-off-by: NAndrew Morton <akpm@linux-foundation.org>
      Signed-off-by: NLinus Torvalds <torvalds@linux-foundation.org>
      bab55417
  23. 04 1月, 2012 2 次提交
  24. 01 8月, 2011 1 次提交
  25. 16 9月, 2010 1 次提交
  26. 10 9月, 2010 1 次提交
  27. 29 4月, 2010 1 次提交
  28. 04 12月, 2009 1 次提交
  29. 03 10月, 2009 1 次提交
  30. 11 9月, 2009 1 次提交
    • J
      block: add blk-iopoll, a NAPI like approach for block devices · 5e605b64
      Jens Axboe 提交于
      This borrows some code from NAPI and implements a polled completion
      mode for block devices. The idea is the same as NAPI - instead of
      doing the command completion when the irq occurs, schedule a dedicated
      softirq in the hopes that we will complete more IO when the iopoll
      handler is invoked. Devices have a budget of commands assigned, and will
      stay in polled mode as long as they continue to consume their budget
      from the iopoll softirq handler. If they do not, the device is set back
      to interrupt completion mode.
      
      This patch holds the core bits for blk-iopoll, device driver support
      sold separately.
      Signed-off-by: NJens Axboe <jens.axboe@oracle.com>
      5e605b64
  31. 01 7月, 2009 1 次提交
    • J
      block: get rid of queue-private command filter · 018e0446
      Jens Axboe 提交于
      The initial patches to support this through sysfs export were broken
      and have been if 0'ed out in any release. So lets just kill the code
      and reclaim some space in struct request_queue, if anyone would later
      like to fixup the sysfs bits, the git history can easily restore
      the removed bits.
      Signed-off-by: NJens Axboe <jens.axboe@oracle.com>
      018e0446
  32. 09 2月, 2009 1 次提交
  33. 09 10月, 2008 2 次提交
  34. 03 7月, 2008 1 次提交